编程题
### 题目大意 给你一棵 $n$ 个节点的树,一开始所有结点权值都为 $0$,一共有 $n-1$ 条边,每条边连接 $a_i$ 和 $b_i$。 一共进行 $𝑚$ 次操作。每次操作有 $2$ 种: + $t_i = 1$,以 $a_{e_i}$ 为起点遍历所有的点且路径上不能经过 $b_{e_i}$,路径上的所有点加 $x_i$。 + $t_i = 2$,以 $b_{e_i}$ 为起点遍历所有的点且路径上不能经过 $a_{e_i}$,路径上的所有点加 $x_i$。 问最终每个点的权值是多少。 ### 输入格式 第一行输入包含一个整数 $n$,表示树的结点的数量。 接下来 $n - 1$ 行包含两个用空格分开的数字 $a_i,b_i$,表示树的边。 下一行包含一个整数 $q$ ,表示操作的数量。 接下来 $q$ 行包括三个用空格分隔的整数 $t_i,e_i,x_i$,$t_i$ 表示操作的类型,$e_i$ 表示操作的边的编号,$x_i$ 是每次操作需要加上的权值。 ### 输出格式 处理完所有查询后,从结点 $1$ 到结点 $n$ 打印每个结点的权值。 ### 样例输入 ```txt 5 1 2 2 3 2 4 4 5 4 1 1 1 1 4 10 2 1 100 2 2 1000 ``` ### 样例输出 ```txt 11 110 1110 110 100 ``` ### 样例说明 在第一个查询中,我们将在不访问顶点 $2$ 的情况下,从顶点 $1$ 到达的每个顶点的权值都增加 $1$,即顶点 $1$。 在第二个查询中,我们将在不访问顶点 $5$ 的情况下,从顶点 $4$ 到达的每个顶点的权值都增加 $10$,即顶点 $1,2,3,4$。 在第三个查询中,我们将在不访问顶点 $1$ 的情况下,从顶点 $2$ 到达的每个顶点的权值都增加 $100$,即顶点 $2,3,4,5$。 在第四个查询中,我们将在不访问顶点 $2$ 的情况下,从顶点 $3$ 到达的每个顶点的权值都增加 $1000$,即顶点 $3$。 ### 评测数据规模 对于 $100$% 的评测数据,$1\leq n ,q \leq 200000,1 \leq x\leq 10^9,1\leq t_i \leq 2,1\leq a_i, b_i \leq n,a_i \neq b_i,1 \leq e_i \leq n - 1$。
查看答案
赣ICP备20007335号-2