mydcwfy's Blog

CF1606F Tree Queries

Posted on
Symbols count in article: 3.2k Reading time ≈ 7 mins.

题意：给定一棵 $n$ 的点的根为 1 的树，定义一次操作为把 $x$ 的所有儿子接到 $x$ 父亲处，并删除 $x$。$q$ 次询问给定 $u, k$，输出任意操作之后 $son(u) - mk$ 的最大值，$m$ 表示操作次数。$n, q\leq 2 \times 10 ^ 5$，6s。

比较经典，但是没做过，于是 vp 时没有思路……

首先考虑暴力 DP 的过程，记 $f(u)$ 表示把 $u$ 删除，在删除前的儿子个数（定义比较奇怪？），容易得到转移式：

考虑对其进行化简，记 $s_u$ 表示 $u$ 在原树上的儿子，然后可以得到：

注意到如果 $f(v) - k - 1 < 0$ 的话，我们可以认为 $(u, v)$ 不连通，从而达到对 $0$ 取 $\max$ 的效果。

现在忽视掉 $\max$ 的话，我们可以写出比较好的形式：

$sum_u$ 表示在联通树上在 $u$ 子树内部的原树度数和，所以 $sum_u$ 不是 $sz_u - 1$，需要注意。

根据这个式子，由于 $f(u)$ 要 $\geq 1$ 才会被认为是向父亲连边了，于是我们可以得到 $k\leq \dfrac {sum_u}{sz_u} - 1$ 时 $f(u)$ 相当于是向父亲连边。

改变联通性过后，$fa(u)\to top(u)$ 的 $sum$ 和 $sz$ 都会发生变化，同理他们的 $k$ 的阈值也会发生变化。但是注意到只有 $top(u)$ 的阈值时受关注的，因为其他点都已经向父亲联通了。修改这个可以使用差分转化为单点加子树查，于是树状数组可以做到 $O(n\log n)$。

维护所有的阈值只需要用一个 std::priority_queue 维护，计算时将询问按 $k$ 从大到小处理即可。注意 $top(u)$ 联通性改变过后，他的阈值一定是变大，所以没必要删除原来的。复杂度 $O(n\log n)$，轻松通过。

总结：树上取 $\max / \min$ 时可以转化为和 0 比较，使用连通性去掉 $\max / \min$。

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
struct Fenwick {
	int tr[N];
	void add(int x, int c) {
		if (!x) return puts("Failed"), void();
		for (; x < N; x += (x & -x)) tr[x] += c;
	}
	int ask(int x) {
		int res = 0;
		for (; x; x ^= (x & -x)) res += tr[x];
		return res;
	}
} T1, T2;

inline int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

void dfs(int x, int fa = 0)
{
	nw[dfn[x] = ++ *dfn] = x, ::fa[x] = fa, sz[x] = 1;
	for (int v : g[x])
		if (v ^ fa) dfs(v, x), sz[x] += sz[v];
}

int ask(Fenwick &T, int x) { return T.ask(dfn[x] + sz[x] - 1) - T.ask(dfn[x] - 1); }

void update(int x)
{
	if (vis[x] || x == 1) return;
	vis[x] = true;
	assert(f[x] == x);
	int sz = ask(T1, x), sum = ask(T2, x), anc;
	f[x] = find(fa[x]), anc = find(x);
	// std::cout << "Update " << x << ' ' << sz << ' ' << fa[x] << ' ' << find(fa[x]) << std::endl;
	T2.add(dfn[fa[x]], sum), T1.add(dfn[fa[x]], sz);
	if (fa[anc]) T1.add(dfn[fa[anc]], -sz), T2.add(dfn[fa[anc]], -sum);
	assert(ask(T1, anc) >= 0 && ask(T2, anc) >= 0);
	pq.push({ask(T2, anc) / ask(T1, anc) - 1, anc});
}

signed main()
{
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) f[i] = i;
	for (int i = 1, u, v; i < n; ++ i)
	{
		scanf("%lld %lld", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	std::cin >> Q;
	for (int i = 1; i <= Q; ++ i) scanf("%lld %lld", &q[i].u, &q[i].k), q[i].id = i;
	std::sort(q + 1, q + Q + 1, [&](Query &q1, Query &q2) {
		return q1.k > q2.k;
	});
	dfs(1);
	for (int i = 1; i <= n; ++ i) {
		T1.add(dfn[i], 1), son[i] = g[i].size() - (i > 1);
		T2.add(dfn[i], son[i]);
		if (i ^ 1)
			T1.add(dfn[fa[i]], -1), T2.add(dfn[fa[i]], -son[i]), pq.push({son[i] - 1, i});
	}
	for (int i = 1, x; i <= Q; ++ i) {
		while (!pq.empty() && pq.top().first >= q[i].k)
			x = pq.top().second, pq.pop(), update(x);
		// std::cout << "Query " << q[i].u << ' ' << q[i].k << ' ' << ask(T1, q[i].u) << ' ' << ask(T2, q[i].u) << '\n';
		res[q[i].id] = ask(T2, q[i].u) - (q[i].k + 1) * ask(T1, q[i].u) + 1 + q[i].k;
		// res[q[i].id] = std::max(res[q[i].id], (int) g[q[i].u].size() - 1);
	}
	for (int i = 1; i <= Q; ++ i) printf("%lld\n", res[i]);
	return 0;
}