CF1797D.Li Hua and Tree
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Li Hua has a tree of n vertices and n−1 edges. The root of the tree is vertex 1 . Each vertex i has importance ai . Denote the size of a subtree as the number of vertices in it, and the importance as the sum of the importance of vertices in it. Denote the heavy son of a non-leaf vertex as the son with the largest subtree size. If multiple of them exist, the heavy son is the one with the minimum index.
Li Hua wants to perform m operations:
- "1 x " ( 1≤x≤n ) — calculate the importance of the subtree whose root is x .
- "2 x " ( 2≤x≤n ) — rotate the heavy son of x up. Formally, denote sonx as the heavy son of x , fax as the father of x . He wants to remove the edge between x and fax and connect an edge between sonx and fax . It is guaranteed that x is not root, but not guaranteed that x is not a leaf. If x is a leaf, please ignore the operation.
Suppose you were Li Hua, please solve this problem.
输入格式
The first line contains 2 integers n,m ( 2≤n≤105,1≤m≤105 ) — the number of vertices in the tree and the number of operations.
The second line contains n integers a1,a2,…,an ( −109≤ai≤109 ) — the importance of each vertex.
Next n−1 lines contain the edges of the tree. The i -th line contains two integers ui and vi ( 1≤ui,vi≤n , ui=vi ) — the corresponding edge. The given edges form a tree.
Next m lines contain operations — one operation per line. The j -th operation contains two integers tj,xj ( tj∈{1,2} , 1≤xj≤n , xj=1 if tj=2 ) — the j -th operation.
输出格式
For each query "1 x ", output the answer in an independent line.
输入输出样例
输入#1
7 4 1 1 1 1 1 1 1 1 2 1 3 2 4 2 5 3 6 6 7 1 6 2 3 1 6 1 2
输出#1
2 3 3
输入#2
10 14 -160016413 -90133231 -671446275 -314847579 -910548234 121155052 -359359950 83112406 -704889624 145489303 1 6 1 10 10 8 1 4 3 4 2 7 2 5 3 2 9 8 1 4 2 2 2 4 1 4 1 10 2 10 1 9 1 6 2 8 2 10 1 5 1 8 1 1 2 5
输出#2
-2346335269 -314847579 -476287915 -704889624 121155052 -1360041415 228601709 -2861484545
说明/提示
In the first example:
The initial tree is shown in the following picture:
The importance of the subtree of 6 is a6+a7=2 .
After rotating the heavy son of 3 (which is 6 ) up, the tree is shown in the following picture:
The importance of the subtree of 6 is a6+a3+a7=3 .
The importance of the subtree of 2 is a2+a4+a5=3 .