OpenJudge

1023:Challenge 23

总时间限制:
20000ms
单个测试点时间限制:
2000ms
内存限制:
256000kB
描述

维护一棵n个节点的树(n<=10^5),两点间边权d_ij满足(1<=d_ij<=1000),每个节点有黑白两种颜色,支持如下3种,m个操作(m<=10^5):

opt=0.修改第k条边边权成为w

opt=1.将某个节点x颜色取反(黑白互换)

opt=2.询问x节点到距离节点x的最远的黑点的距离,若不存在黑点,则输出-1。



输入
第一行一个数n
第二行n个数a[i]表示第i个点的颜色,当a[i]=1时i点为黑色,反之为白色
接下来n-1行,每行3个数x,y,d_xy,表示一条树边
接下来一行一个数m,表示操作数
接下来m行每行一个数opt,以及当opt=0时两个数k,w,或opt=1,2时的一个数x
输出
对于每个opt=2的操作,输出答案。
样例输入
5
0 0 1 1 0 
1 2 2
2 3 9
2 4 9
2 5 10
8
0 3 9
2 5
1 3
2 5
0 3 6
0 2 9
1 5
2 2
样例输出
19
19
10
来源
mhy12345

请大家尽量使用非暴力的在线做法
部分题目可尝试多种解法
C++选手尽量不用STL容器

全局题号
8439
添加于
2015-06-09
提交次数
5
尝试人数
4
通过人数
3