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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| #include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 300010; const ll INF = 1e15;
int n, rt, m; ll a[N], rtw;
vector<int> e[N];
struct Heap {
multiset<ll> tr;
inline void del(const ll &x) { tr.erase(tr.find(x)); }
inline void add(const ll &x) { tr.insert(x); }
inline ll top() { assert(!tr.empty()); return *(--tr.end()); }
}; Heap hp;
struct Pretree {
int tot, rt, lf[N * 40], rf[N * 40], cnt[N * 40]; ll s[N * 40];
void mdy(int &u, ll l, ll r, ll x, int w) {
if(!u) u = ++tot; s[u] += x * w, cnt[u] += w; if(l >= r) return ;
ll mid = (l + r) / 2;
x <= mid ? mdy(lf[u], l, mid, x, w) : mdy(rf[u], mid + 1, r, x, w);
}
ll ask(int u, ll l, ll r, int k) {
if(cnt[u] <= k) return s[u]; if(l >= r) return l * k;
ll mid = (l + r) / 2;
if(cnt[rf[u]] >= k) return ask(rf[u], mid + 1, r, k);
return s[rf[u]] + ask(lf[u], l, mid, k - cnt[rf[u]]);
}
}; Pretree t;
struct LCT {
#define lc ch[0][u]
#define rc ch[1][u]
int ch[2][N], fa[N], rt; bool lz[N]; int sta[N], top; ll s[N];
inline bool nroot(const int &u) { return ch[0][fa[u]] == u || ch[1][fa[u]] == u; }
inline void rev(const int &u) { swap(lc, rc), lz[u] ^= 1; }
inline void pushup(const int &u) { s[u] = s[lc] + s[rc] + a[u]; }
inline void pushdown(const int &u) { if(lz[u]) rev(lc), rev(rc), lz[u] = 0; }
void rotate(int u) {
int y = fa[u], z = fa[y], k = ch[1][y] == u, w = ch[k ^ 1][u];
if(nroot(y)) ch[ch[1][z] == y][z] = u; ch[k][y] = w, ch[k ^ 1][u] = y;
if(w) fa[w] = y; fa[y] = u, fa[u] = z; pushup(y), pushup(u);
}
void splay(int u) {
int y = u, z; for(sta[top = 1] = y; nroot(y); sta[++top] = y = fa[y]);
for(; top; pushdown(sta[top--]));
for(; nroot(u); rotate(u)) {
y = fa[u], z = fa[y];
if(nroot(y)) rotate((ch[0][z] == y) ^ (ch[0][y] == u) ? u : y);
}
}
void Link(int x, int y) {
t.mdy(t.rt, 0, INF, s[x], -1), t.mdy(t.rt, 0, INF, s[y], -1);
t.mdy(t.rt, 0, INF, s[ch[1][x]], 1), ch[1][x] = y, pushup(x);
t.mdy(t.rt, 0, INF, s[x], 1);
}
bool check(int u) {
splay(rt); int y = u; for(; nroot(y); y = fa[y]); splay(u); return y == rt;
}
inline int Right(int u) { for(; rc; u = rc); return u; }
void access(int u) {
int y = u; splay(u), u = fa[u];
for(; u; u = fa[y = u]) {
splay(u);
if(check(u) && s[lc] < s[rc]) rt = Right(u), splay(rt), rev(rt), splay(u);
if(s[rc] < s[y]) Link(u, y); else return ;
}
}
#undef lc
#undef rc
}; LCT lct;
void dfs(int u, int ff, ll d) {
d += a[u]; if(d > rtw) rtw = d, rt = u; for(auto v : e[u]) if(v != ff) dfs(v, u, d);
}
void init(int u, int ff) {
ll d = 0; int son = 0;
for(auto v : e[u]) if(v != ff) {
lct.fa[v] = u, init(v, u); if(lct.s[v] > d) d = lct.s[v], son = v;
}
lct.ch[1][u] = son, lct.pushup(u);
for(auto v : e[u]) if(v != ff && v != son) t.mdy(t.rt, 0, INF, lct.s[v], 1);
}
int main() {
scanf("%d", &n);
rep(i, 2, n) { int x, y; scanf("%d%d", &x, &y), e[x].pb(y), e[y].pb(x); }
rep(i, 1, n) scanf("%lld", &a[i]), hp.add(a[i]);
dfs(1, 0, 0); int trt = rt; rt = rtw = 0, dfs(trt, 0, 0);
init(trt, 0), lct.rt = trt, t.mdy(t.rt, 0, INF, rtw, 1);
for(scanf("%d", &m); m; --m) {
int opt; scanf("%d", &opt);
if(!opt) {
int x, y; scanf("%d%d", &x, &y), lct.splay(x);
hp.del(a[x]), t.mdy(t.rt, 0, INF, lct.s[x], -1);
a[x] += y, lct.pushup(x);
hp.add(a[x]), t.mdy(t.rt, 0, INF, lct.s[x], 1);
lct.access(x);
}
else {
int k; scanf("%d", &k);
if(k == 1) printf("%lld\n", hp.top());
else printf("%lld\n", t.ask(t.rt, 0, INF, k - 1));
}
}
return 0;
}
|