/ Vijos / 题库 /

有趣的逛街

有趣的逛街

描述

这是一个太阳从西边升起的情人节,木姑娘邀请我一起去逛街。

城市道路被描绘成一个树形结构,由n个路口组成。

今天实在是太反常了,每一个路口都被挂起来了一盏可变色的灯笼,其中有些是红色的灯笼,有些是蓝色的灯笼。

一个奇怪的政策,仅限于今天,要求在路口u的人群,只能移动到所有同色的路口v,且u到v的道路上所有路口也都有着相同颜色的灯笼。

每一处路口都被赋予了权值w[i],诠释了这个路口对于木姑娘的吸引力。

带木姑娘去那些最吸引她的路口,就是今天白天的任务。

格式

输入格式

第一行给出路口数n,1<=n<=100000。
之后n-1行,每行给出两个数(u,v)描绘了一条连接u和v的道路。1<=u,v<=n。
之后1行,给出了n个0或1的整数,表示了每一个路口灯笼的颜色。
之后1行,给出了n个整数w[1],w[2],...,w[n]表示了每一个路口的权值。
再下面一行,给出整数m,表示询问和修改的总数,1<=m<=100000。
之后m行,每行提供一条询问,或修改操作,满足下述三种形式:
0 u : 询问从路口u出发,可以到达的最有吸引力的路口。
1 u : 修改路口u的灯笼颜色。
2 u w : 将路口u的权值修改为w。

输出格式

对于每一次询问,输出目标路口的权值。(即可以抵达的有着最大权值的路口的权值)

样例1

样例输入1

5
1 2
1 3
1 4
1 5
0 1 1 1 1
1 2 3 4 5
3
0 1
1 1
0 1

样例输出1

1
5

样例2

样例输入2

7
1 2
1 3
2 4
2 5
3 6
3 7
0 0 0 0 0 0 0
1 2 3 4 5 6 7
4
0 1
1 1
0 2
0 3

样例输出2

7
5
7

限制

对于30%的数据,n,m<=10。
存在40%的数据,n,m<=100000,城市交通网形成的树结构的高度不超过256。
对于100%的数据,n,m<=100000,所有权值为绝对值不超过1000000000的整数。

信息

ID
1936
难度
8
分类
a 点击显示
标签
(无)
递交数
19
已通过
5
通过率
26%
被复制
2
上传者

相关