F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 2566. -- xmastree

2566: xmastree

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 288  Solved: 127
[Submit][Status][Discuss]

Description

  有一棵含N个结点的树,树上每条边(ai,bi)都有一个权值wi。树上每个结点涂有一个初始颜色ci。现在有很多次修改操作,第i次修改会将结点xi的颜色修改成yi。请在所有修改前和每次修改之后输出一个数,表示对应时刻最近的同色结点对的距离。
  其中,距离定义为树上两点的最短路的距离。最短路按边的权值wi计算。

Input

  第一行一个数N。第二行N个数依次给出每个结点的初始颜色ci
  下面N-1行每行三个数ai,bi,wi,表示一条权值为wi的树边(ai,bi)
  下面一个数M表示修改次数。
  下面M行每行两个数xi,yi,表示将结点xi的颜色修改为yi

Output

  输出包含M+1行,第一行表示初始局面的最近同色结点对距离,下面M行依次表示每次修改后的最近同色结点对距离。如果某时刻没有同色点对,则在对应行输出-1

Sample Input

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

Sample Output

2
3
8
2
9

HINT

样例说明

  每行输出对应的解释为:

  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

 

Source

2012国家集训队Round 1 day3

[Submit][Status][Discuss]

HOME Back