#PQJ2758x15145. QOJ 2758_15145
QOJ 2758_15145
2 4 2 【输出样例2】 17 【样例解释】 在第二个样例中,将点1,2 染黑就能获得最大收益。 【数据范围】 对于30%的数据,N<=20; 对于50%的数据,N<=100; 对于100%的数据,0<=K<=N。 T2(T2.in | T2.out | T2.cpp) 时间限制:1S 空间限制:256MB 【题目描述】 有一棵点数为N 的树,以点1 为根,且树点有边权。然后有M 个 操作,分为三种: 操作1:把某个节点x 的点权增加a。 操作2:把某个节点x 为根的子树中所有点的点权都增加a。 操作3:询问某个节点x 到根的路径中所有点的点权和。 【输入格式】 输入文件为T2.in。 文件第一行包含两个整数N, M。表示点数和操作数。 接下来一行N 个整数,表示树中节点的初始权值。 接下来N-1 行每行三个正整数fr, to,表示该树中存在一条边(fr, to)。
再接下来M 行,每行分别表示一次操作。其中第一个数表示该操 作的种类(1-3),之后接这个操作的参数(x 或者x a)。 【输出格式】 输出文件为T2.out。 对于每个询问操作,输出该询问的答案。答案之间用换行隔开。 【输入样例】 5 5 1 2 3 4 5 1 2 1 4 2 3 2 5 3 3 1 2 1 3 5 2 1 2 3 3 【输出样例】 6 9 13 【数据范围】 对于30%的数据,N,M<=1000; 对于50%的数据,N,M<=100000 且数据随机; 对于100%的数据,N,M<=100000,且所有输入数据的绝对值都不 会超过10^6。