1 条题解
-
1湖中小岛 LV 8 @ 2024-07-31 10:54:49
/ 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
Copy
样例输出1
3
2
Copy
限制
存在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
- 1