1016 - Black-White Tree
Time Limit : 30 Second
Memory Limit : 256 MB
Submission: 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