CF - D. Reset K Edges（二分答案，模拟）

https://codeforces.com/contest/1739/problem/D

题意
给定一棵根节点为 1 的树。

可以执行下面的操作不超过 k 次：

• 选择一条边 $(v,u)$ 删掉，v 是 u 的父节点；
• 增加一条边 $(1,u)$，即让 u 与根节点相连。

定义树的高度为最深的节点深度，根节点深度为 0。

问，树的高度最小为多少？

$2\le n\le 2\cdot 10^5;0\le k\le n-1$

思路
让最深的节点深度最小，而操作数越多树的高度便越小，满足单调性，考虑二分最终树的高度。

对于深度最深的节点深度 mid 确定了，所有节点的深度都要小于这个值，不满足就执行操作，看最终执行的操作次数是否小于等于 k，如果是，mid 就能达到，继续减小。

在树中，从上到下节点数和边数都呈递增之势，如果操作肯定要尽量在上面，把上面的节点接到根结点上，下面其子节点深度自然减小。这样贪心，操作次数最少。

按照深度从大到小遍历所有节点，如果其最大子树高度大于等于 mid 了，并且其父节点不是根节点，那么就需要将该节点和根节点相连，操作数 +1。

而这个节点移动过去了，却不能在原树上改，后面的二分判断还要用。那么如何判断每个节点的最大子树高度呢？

一开始是这样想的，对于每个节点开一个 multiset，存下所有子节点所在子树的高度。一旦一个节点和根节点相连了，就把其父节点的 multiset 中删掉其所在子树高度。每次只要取 set 里的最大值判断当前节点的真实子树高度。但是对每个点都开 multiset，不知道会不会超时或者爆空间。

然后发现直接记录就行，用 cnt[i] 存下所有子节点所在子树的最大高度，从下往上走的时候把父节点更新，或者对于每个节点遍历所有子节点的 cnt[i] 取最大值都可。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int k;
struct node{
	int id;
	int dep;
}a[N];
int cnt[N];
vector<int> e[N];
int pre[N];

bool cmp(node a, node b){
	return a.dep > b.dep;
}

void bfs()
{
	queue<int> que;
	que.push(1);
	
	while(que.size())
	{
		int x = que.front(); que.pop();
		
		for(int tx : e[x])
		{
			a[tx].dep = a[x].dep + 1;
			que.push(tx);
		}
	}
}

bool check(int mid)
{
	for(int i=1;i<=n;i++) cnt[i] = 1;
	
	int ans = 0;
	for(int i=1;i<=n;i++)
	{
		int x = a[i].id;
		for(int tx : e[x])
		{
			cnt[x] = max(cnt[x], cnt[tx] + 1);
		}
		if(cnt[x] >= mid && pre[x] != 1 && x != 1)
		{
			ans ++;
			cnt[x] = 0;
		}
	}
	
	if(ans > k) return 0;
	return 1;
}

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> n >> k;
		for(int i=1;i<=n;i++) e[i].clear(), a[i].id = i, cnt[i] = 1;
		
		for(int i=2;i<=n;i++)
		{
			int x; cin >> x;
			e[x].push_back(i);
			pre[i] = x;
		}
		
		a[1].dep = 0;
		bfs();
		
		sort(a+1, a+n+1, cmp);
		
		int l = 1, r = 2e5;
		while(l < r)
		{
			int mid = l + r >> 1;
			if(check(mid)) r = mid;
			else l = mid + 1;
		}
		cout << l << endl;
	}

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

---

C 题没有思路该先去看一眼 D 的啊！！