/
dynamic_tree_vertex_add_subtree_sum.test.cpp
68 lines (55 loc) · 1.2 KB
/
dynamic_tree_vertex_add_subtree_sum.test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_subtree_sum
#include<bits/stdc++.h>
using namespace std;
#define call_from_test
#include "../../linkcuttree/base.cpp"
#include "../../linkcuttree/subtree.cpp"
#undef call_from_test
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
const char newl = '\n';
using ll = long long;
int n,q;
cin>>n>>q;
vector<ll> as(n);
for(int i=0;i<n;i++) cin>>as[i];
using Node = NodeBase<ll>;
constexpr size_t LIM = 2e5+100;
using LCT = Subtree<Node, LIM>;
LCT lct;
for(int i=0;i<n;i++) lct.create(as[i]);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
lct.evert(lct[v]);
lct.link(lct[u],lct[v]);
}
for(int i=0;i<q;i++){
int t;
cin>>t;
if(t==0){
int u,v,w,x;
cin>>u>>v>>w>>x;
lct.evert(lct[u]);
lct.cut(lct[v]);
lct.evert(lct[x]);
lct.link(lct[w],lct[x]);
}
if(t==1){
int p,x;
cin>>p>>x;
as[p]+=x;
lct.set_val(lct[p],as[p]);
}
if(t==2){
int v,p;
cin>>v>>p;
lct.evert(lct[p]);
lct.cut(lct[v]);
cout<<lct.query(lct[v])<<newl;
lct.link(lct[p],lct[v]);
}
}
return 0;
}