1 条题解

  • 1
    @ 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

信息

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