黄金体验

发表于
https://cometoj.com/contest/58/problem/F?problem_id=2762

题目链接

黄金体验

题意

给出一颗有 $ n $ 个节点的树，每个点有一个初始权值 $ w_i $ ，要求支持两种操作：

  1. 给出 $ x $ ，$ y $ ，使点 $ x $ 的权值增加 $ y $。
  2. 给出 $ k $，选定 $ k $ 个点使得包含这 $ k $ 个点的最小联通子图点权和最大，你只需要输出这个最大值。
    $ n, q \leq 100000, w_i, y \leq 10^9 $

做法

先不考虑修改操作，对于询问操作，当 $ k = 1 $ 时为点权最大值，可以直接 $ O(1) $ 维护。当 $ k = 2 $ 时，答案为点权最大的一条边（显然是一个叶子连向另一个叶子）；当 $ k $ 更大时，相当于在已有的图上加一条未选过的从叶子上来的权值最大的链。
所以可以权值长链剖分，用动态开点线段树维护前 $ k - 1 $ 大的链。
考虑加上修改，由于点权只会增大，所以原本的修改点所在的长链依旧是长链，不是长链则可能更新成长链。可能会更新直径（要 $ makeroot $），这部分可以用 $ LCT $ 维护。
时间复杂度 $ O(n \log^2 n) $ 。 

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;
}