#P17999. Traffic Lights
Traffic Lights
Traffic Lights
题目描述
给定一棵树,每个顶点的灯泡为红色、黄色或绿色之一。
一条“交通灯路径”是树上的一条简单路径,两个端点分别为红色和绿色,并且至少有一个内部顶点为黄色。路径长度为其包含的边数;路径上其他顶点的颜色没有额外限制。
处理两类操作:
1 v c:将顶点 的颜色改成 。2 v:保证当前 为黄色,求经过 的最短交通灯路径长度;不存在时输出 。
输入格式
第一行一个整数 ,。
每个测试用例先输入 ,满足 。
接下来 行,每行两个整数 ,表示一条边,满足 、。保证这些边构成树。
随后一行长度为 的字符串,第 个字符表示顶点 的初始颜色:R 为红色,Y 为黄色,G 为绿色。
接下来 行描述操作,其中 , 为 R、Y、G 之一。每组至少有一次第 2 类操作,且该操作的查询顶点当时一定为黄色。
所有测试用例的 之和、 之和分别不超过 。
输出格式
按顺序对每次第 2 类操作输出一个整数,表示答案。
样例 1
输入
1
7 7
1 2
2 3
2 4
4 5
4 6
6 7
RYGYRGY
2 2
1 7 G
2 4
1 1 Y
2 2
1 5 Y
2 4
输出
2
2
3
-1
样例 2
输入
3
3 2
1 2
2 3
YRG
2 1
1 1 Y
4 3
1 2
2 3
2 4
RYGY
2 2
1 1 Y
2 4
5 8
1 2
2 3
3 4
3 5
YRYGY
2 3
1 5 G
2 1
1 2 Y
2 3
1 1 R
2 3
1 4 Y
输出
-1
2
-1
2
-1
-1
3