1016 - Black-White Tree

Time Limit: 30s Memory Limit: 256MB

Submissions: 851 Solved: 213
Description
在图论中,包含n个结点(结点编号为1~n)、n-1条边的无向连通图被称为树。 在树中,任意一对结点间的简单路径总是惟一的。 你拥有一棵白色的树——所有节点都是白色的。接下来,你需要处理c条指令: 修改指令(0 v):改变一个给定结点的颜色(白变黑,黑变白); 查询指令(1 v):询问从结点1到一个给定结点所经过的第一个黑色结点编号(假设沿着简单路径走)。 注意,在查询指令中,必须从结点1而不是结点v出发。如果结点1本身就是黑色,查询指令应该返回1。
Input
第一行包含两个正整数n, c,即结点数和指令条数,n和c都不大于1,000,000. 以下n-1行,每行两个正整数(ui, vi) (1 <= ui < vi <= n),表示结点ui到vi之间有一条无向边。 以下c行,每行两个整数(c, v)。当c=0时表示修改指令,其中v代表被修改的结点编号;c=1时表示查询指令。 你的程序需要输出结点1到结点v之间路径的第一个黑色结点编号。 在第一条指令执行前,所有结点都是白色的。
Output
对于每个查询操作(c=1的操作),输出一行,包含一个整数,即第一个黑色结点的编号。如果不存在黑色结点,输出-1。
Sample Input
9 8
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
1 3
0 8
1 6
1 7
0 2
1 9
0 2
1 9 
Sample Output
-1
8
-1
2
-1 
Hint
Source
AStar 2008