【题解】CF1606F Difficult Mountain

Posted on Edited on

考场甚至没能看到这题属实是拉了, 于是记录一下这个巧妙的题.

简要题意

给定一棵 $n$ 个点的树, 以及 $q$ 次询问, 每次询问两个数 $x,k$ , 求在以 $x$ 为根的子树内删除 $m$ 个节点, 删除一个节点意为将该的儿子连向该点的父亲并删除该点, 使得 $cnt(x)-m\times k$ 最大, 其中 $cnt(x)$ 为 $x$ 的儿子个数, 询问独立.

$n,q \leqslant 2\times 10^5$ .

题解

首先很显然的是答案不可能小于 $0$ , 这对 $m$ 和 $k$ 就有了极大的限制.

考虑对 $k$ 进行分治, 在 $k \leqslant \sqrt{n}$ 的时候, 直接 $dp$ , 设 $f_{i,j}$ 为在以 $i$ 为根的子树内 $k = j$ 时的答案.

此部分复杂度为 $\mathcal{O}(n \sqrt{n})$ .

在 $k \geqslant \sqrt{n}$ 的时候, 必有 $m \leqslant \sqrt{k}$ , 这样的话考虑树形背包, 记 $g_{i,j}$ 为在以 $i$ 为根的子树内删 $j$ 个点的最大儿子数, 考虑每个儿子删不删.

此部分复杂度为 $\mathcal{O}(n \sqrt{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
/************************************************
*Author        :  demonlover
*Created Time  :  2021.11.07.10:36
*Problem       :  CF1606F
************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
typedef pair <ll,ll> pll;
#define DEBUG(x) cout << #x << " = " << x << endl
template <typename T>
inline bool read(T &x) {
	int f = 1,c = getchar();x = 0;
	while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
	while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
	return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
	return read(x) && read(args...);
}

namespace run {
	const int maxn = 2e5+10;
	const int B = 450;
	struct Edge {int nxt,to;}edge[maxn<<1];
	int begn[maxn],e;
	inline void add(int x,int y) {
		edge[++e] = (Edge){begn[x],y};begn[x] = e;
		return;
	}
	int g[B+10],siz[maxn],f[maxn][B+10];
	ll ans[maxn];
	int n,m;
	vector< pair< pll,int > > q[2];
	inline void dfs1(int x,int fa) {
		for (register int i = begn[x];i;i = edge[i].nxt) {
			int y = edge[i].to;
			if (y ^ fa) {
				dfs1(y,x);
				for (register int j = 0;j <= B;++j)
					f[x][j] = max(f[x][j]+1,f[x][j]-j+f[y][j]);
			}
		}
		return;
	}
	inline void dfs2(int x,int fa) {
		memset(f[x],-0x3f,sizeof(f[x]));
		memset(g,-0x3f,sizeof(g));
		siz[x] = 1;
		f[x][0] = 0;
		for (register int i = begn[x];i;i = edge[i].nxt) {
			int y = edge[i].to;
			if (y ^ fa) {
				dfs2(y,x);
				for (register int j = 0;j <= siz[x] && j <= B;++j) {
					for (register int k = 0;k <= siz[y] && j+k <= B;++k) {
						g[j+k] = max(g[j+k],f[x][j]+1);
						g[j+k+1] = max(g[j+k+1],f[x][j]+f[y][k]);
					}
				}
				siz[x] += siz[y];
				for (register int j = 0;j <= siz[x] && j <= B;++j)f[x][j] = g[j],g[j] = -0x3f3f3f3f;
			}
		}
		return;
	}
	inline int main() {
		read(n);
		for (register int i = 1,x,y;i < n;++i) {
			read(x,y);add(x,y);add(y,x);
		}
		read(m);
		for (register int i = 1;i <= m;++i) {
			ll x,k;
			read(x,k);
			if (k > B)q[1].push_back(make_pair(pll(x,k),i));
			else q[0].push_back(make_pair(pll(x,k),i));
		}
		dfs1(1,0);
		for (auto i : q[0])
			ans[i.second] = f[i.first.first][i.first.second];
		dfs2(1,0);
		for (auto i : q[1])
			for (register int j = 0;j <= B;++j) {
				ans[i.second] = max(ans[i.second],(ll)f[i.first.first][j]-j*i.first.second);
			}
		for (register int i = 1;i <= m;++i)printf("%lld\n",ans[i]);
		cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
		return 0;
	}
}

#define demonlover
int main() {
#ifdef demonlover
	freopen("CF1606F.in","r",stdin);
	freopen("CF1606F.out","w",stdout);
#endif
	return run :: main();
}