Electrical Issues

0

0 votes
Problem

AlphaElectrics is currently having a problem providing electricity to the inhabitants of Alpha Planet! As a result, AlphaElectrics is redesigning its network of electrical cables. AlphaElectrics’ network of cables can be modeled as a graph of N nodes connected by N - 1 edges, where nodes represent power stations and edges represent electrical cables. Power stations are labeled from 1...N. AlphaElectrics categorizes its power stations into M different types. The ith power station has a type si.

AlphaElectrics has Q queries they want to answer, so they have asked you for help! There are two types of queries:

  • Type 1: AlphaElectrics gives you a number x and wants you to find the distance to the closest power station from power station x that is a different type of power station than power station x. The distance between two power stations is the number of electrical cables on the path between them.
  • Type 2: AlphaElectrics tells you that power station x has been changed to type y.

Help AlphaElectrics answer their queries, which will help restore power to the inhabitants of Alpha Planet!

Input Format:

  • The first line of input will give N and M (1 ≤ N ≤ 25,000, 1 ≤ M ≤ 10), the number of power stations and the number of power station types, respectively
  • The second line of input will give N numbers, the ith number being the power station type of power station i
  • The next N - 1 lines will give two numbers, u and v, denoting an electrical cable between power stations u and v. All power stations can reach each other via some path of electrical cables.
  • The next line of input will give Q (1 ≤ Q ≤ 105), the number of queries
  • The next Q lines after that will give the queries. Each line will first give t, the type of query.
    • If t = 1, x will be given, the label of the power station to answer query Type 1
    • If t = 2, x and y will be given, denoting power station x has been changed to type y

Output Format:

For each query of Type 1, output a single number on a new line that represents the distance to the closest power station from power station x that is a different power station type than power station x. If there is no power station with a different power station type than power station x, output -1.

(Problem credit: Justin Li)

Time Limit: 2
Memory Limit: 128
Source Limit:
Editor Image

?