有一棵含N个结点的树,树上每条边(ai,bi)都有一个权值wi。树上每个结点涂有一个初始颜色ci。现在有很多次修改操作,第i次修改会将结点xi的颜色修改成yi。请在所有修改前和每次修改之后输出一个数,表示对应时刻最近的同色结点对的距离。
其中,距离定义为树上两点的最短路的距离。最短路按边的权值wi计算。
其中,距离定义为树上两点的最短路的距离。最短路按边的权值wi计算。
F.A.Qs | Home | ProblemSet | Status | Ranklist | Contest | Login | Register | 捐赠本站 |
---|
样例说明
每行输出对应的解释为:
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