传统题 1000ms 256MiB

我妻云南

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

注意:本题不考虑给定的 aia_i,初始时所有点的点权均视为 0。选手仅需读入给定的 aia_i 并忽略其对答案的影响。

题目背景

戌蛤:然后这个的主要玩法是人物关系

:但是我没有人物关系啊

戌蛤:就是你手里的牌之间关系越多分越多

戌蛤:太假了吧

:这哪里假了啊

戌蛤:突然发现我也想不到什么

戌蛤:比如您和块 -> YNOI 大师

:被您钦定为云南省选带师

戌蛤:有点好奇

戌蛤:我直接把卡牌介绍删了

戌蛤:会挂吗

:我怎么知道(

戌蛤:整个人的 js 我读不太透

戌蛤:整 -> 这

题目描述

给出一棵无根树,点有点权,边有边权。初始时点权均为 00

然后给出 mm 次操作,其中第 ii 次操作会给出两个非负整数 xi,kix_i, k_i,表示对于树上每个点 pp,将 apa_p 累加上 kidist(xi,p)k_i \cdot \operatorname{dist}(x_i, p)。其中 dist(u,v)\operatorname{dist}(u, v) 表示 uu 号点和 vv 号点之间唯一树上路径的边权和。

然后给出 qq 次询问,其中第 ii 次操作会给出三个正整数 li,ri,yil_i, r_i, y_i,表示询问在只保留第 lil_i 次操作到第 rir_i 次操作的情况下,yiy_i 号点的点权是多少。询问互相独立,即每次询问结束后将树的形态恢复至初始。

输入输出格式

输入格式

输入数据的第一行包含三个正整数 n,m,qn, m, q,分别表示树的节点数量,操作的数量和询问的数量。

输入数据的第二行包含 nn 个非负整数 a1,a2,,ana_1, a_2, \dots, a_n。这 nn 个数没有任何作用,请忽略掉它们。

输入数据的接下来 n1n - 1 行,第 ii 行包含三个非负整数 ui,vi,wiu_i, v_i, w_i,表示 uiu_i 号点和 viv_i 号点之间有一条边,边权为 wiw_i

输入数据的接下来 mm 行,第 ii 行包含两个非负整数 xi,kix_i, k_i,表示一次操作。

输入数据的接下来 qq 行,第 ii 行包含三个正整数 li,ri,yil_i, r_i, y_i,表示一次询问。

同一行内的多个数字之间由空格隔开。

输出格式

对于每次询问,输出一行一个整数表示答案。

输入输出样例

5 2 6
0 0 0 0 0
1 2 2
1 3 3
2 4 4
2 5 5
1 1
5 4
1 2 1
1 2 2
1 2 3
1 1 4
1 2 4
1 2 5
28
22
43
6
42
7
10 32 5
4 5 6 2 3 6 9 8 4 1 
1 2 3
2 3 3
2 4 3
2 7 1
3 5 2
5 6 10
5 8 3
7 9 2
9 10 0
4 8
6 10
3 1
10 7
6 7
8 0
9 5
8 3
4 3
8 10
8 9
10 9
8 4
3 0
5 9
6 1
1 6
3 0
3 9
6 9
1 7
10 1
5 9
8 8
4 1
10 2
2 7
1 7
6 2
6 2
2 1
6 2
15 30 3
16 20 4
14 25 10
18 23 9
15 26 10
409
270
550
330
550

样例解释

对于样例 #1,进行完第 11 次操作后树的形态如下如所示

Cr0013Ex1.png

其中边旁边的蓝色数字表示边权,节点圈内的蓝色数字表示标号,节点旁边的红色数字表示边权。

进行完第 22 次操作后树的形态如下如所示

Cr0013Ex2.png

数据范围与约定

1n,m1031 \leqslant n, m \leqslant 10^31q2×1061 \leqslant q \leqslant 2 \times 10^60ai,wi,ki100 \leqslant a_i, w_i, k_i \leqslant 101ui,vi,xi,yin1 \leqslant u_i, v_i, x_i, y_i \leqslant n1lirim1 \leqslant l_i \leqslant r_i \leqslant m

时空限制:1s/256MiB\texttt{1s/256MiB}

最后一个点差不多有这么大

cin/cout 选手注意 IO 用时。

如果您秒了这道题,可以想一想 n,m,q105n, m, q \leqslant 10^5 该怎么做。

2023安徽大学ICPC集训队排位选拔赛 - Round2

未参加
状态
已结束
规则
ACM/ICPC
题目
7
开始于
2023-6-11 14:00
结束于
2023-6-11 18:00
持续时间
4 小时
主持人
参赛人数
26