xmastree
时间限制：10s 空间限制：256MB
题目描述
有一棵含N个结点的树，树上每条边(ai,bi)都有一个权值wi。树上每个结点涂有一个初始颜色ci。现在有很多次修改操作，第i次修改会将结点xi的颜色修改成yi。请在所有修改前和每次修改之后输出一个数，表示对应时刻最近的同色结点对的距离。
其中，距离定义为树上两点的最短路的距离。最短路按边的权值wi计算。
其中，距离定义为树上两点的最短路的距离。最短路按边的权值wi计算。
输入格式
第一行一个数N。第二行N个数依次给出每个结点的初始颜色ci。
下面N-1行每行三个数ai,bi,wi，表示一条权值为wi的树边(ai,bi)。
下面一个数M表示修改次数。
下面M行每行两个数xi,yi，表示将结点xi的颜色修改为yi。
下面N-1行每行三个数ai,bi,wi，表示一条权值为wi的树边(ai,bi)。
下面一个数M表示修改次数。
下面M行每行两个数xi,yi，表示将结点xi的颜色修改为yi。
输出格式
输出包含M+1行，第一行表示初始局面的最近同色结点对距离，下面M行依次表示每次修改后的最近同色结点对距离。如果某时刻没有同色点对，则在对应行输出-1。
样例输入
5 2 2 3 2 3 3 5 9 1 3 1 2 1 2 4 1 8 4 2 3 2 1 1 1 2 2
样例输出
2 3 8 2 9
提示
样例说明
每行输出对应的解释为：
2 -> 最近的是1和2，颜色均为2，距离为2
3 -> 最近的是2和3，颜色均为3，距离为3
8 -> 最近的是1和4，颜色均为2，距离为8
2 -> 最近的是1和2，颜色均为1，距离为2
9 -> 最近的是3和5，颜色均为3，距离为9
数据规模和约定
本题有十个测试点。十个测试点的数据规模如下：
编号 N M 出现过的颜色的总数
1 1000 0 <=10
2 2000 0 <=2000
3 5000 0 <=5000
4 7000 5 <=7000
5 9000 10 <=9000
6 10000 100 <=10000
7 10000 10000 <=50
8 12000 10000 <=12000
9 12000 12000 <=12000
10 12000 12000 <=12000
另外，对于所有数据，有：
1 <= ai <= N, 1 <= bi <= N, 1 <= xi <= N;
1<=wi<=10000
1 <= ci <= 10^9, 1 <= yi <= 10^9
题目来源
2012国家集训队Round 1 day3