/ Vijos / 题库 /

东方明珠下的音乐树

东方明珠下的音乐树

描述

木姑娘来上海玩,这真是我的荣幸。

我带她去了很多狠多地方,等到夜幕降临,我们一起来到了东方明珠下。

适逢音乐节,东方明珠下被人装点了一株音乐树。木姑娘穿着一身白裙子,站在音乐树下,楚楚动人。

音乐树的藤蔓与树叉可以被抽象地看作是一个树结构。每一个结点 x 都对应了一个音符,它的音高为 Hx。

木姑娘每一次会选择两个结点 s 和 t,得到树上的一条路径。我会按照她的指示,去弹奏路径上的音符,弹奏出来的音符会挂在天边。

这样的音乐或许是枯燥的。从 s 出发,到 t 结束。当到达结点 x 的时候,所有音高大于 Sx 的音符会消失,在这之后,会出现一个音高为 Hx 的音符。同样音高的音符可以有很多个。

有的时候,木姑娘还会稍微修正某个结点上的 Sx,为了让这个有音乐的夜晚更加美好。

格式

输入格式

第一行有两个整数N,M ,表示节点数与事件数。
接下来的N-1行,每行两个整数ui,vi ,描述一条连接节点ui与节点vi的边。
接下来的一行,N个整数Hi 。
接下来的一行,N个整数Si 。
接下来的M行,每行表示一个事件,它们的形式如下:
M x val : 将Sx修改为val
Q x y : 如果木姑娘选中了路径x->y,那么在音乐结束(也就是到达终点y的时候)还剩下多少音符。

输出格式

对于每组询问,输出一行答案。

样例1

样例输入1

7 3
1 2
2 3
3 4
4 5
5 6
6 7
3 2 4 5 7 1 2
1 6 3 2 3 4 2
Q 1 7
M 6 1
Q 1 7

样例输出1

3
2

限制

存在15%的数据,1<=N,M<=5000 ,保证给出的边形成一条链,数据中不含M操作。
存在20%的数据,保证给出的边形成一条链,数据中不含M操作。
存在10%的数据,保证给出的边形成一条链。
存在25%的数据,数据中不含M操作。
存在30%的数据,无追加限制。
对于100%的数据,1<=N<=40000,1<=M<=60000,1<=Hi,Si,val<=50000,1<=x,y,ui,vi<=N

信息

ID
1930
难度
10
分类
a 点击显示
标签
(无)
递交数
9
已通过
0
通过率
0%
被复制
3
上传者