【思维】Codeforces Global Round 16 E. Buds Re-hanging
2021-09-17 16:30:00 # ACM

题链

题目解析

给定 $n$ 个节点的树，定义 芽 为：
  $1.$ 芽不是根节点
  $2.$ 至少有一个孩子节点
  $3.$ 所有孩子节点都是叶节点

一次操作被定义为：将一个 芽 取出（包括它的所有孩子节点），连接到不包括被取出的点的任意点上，并作为被连接点的孩子；

可以执行任意多次操作，最终使得整个树的叶子数量最少；

假设芽的数量为 $k$，那么叶子的数量就是 $n-1-k$，一次操作可以将一个芽挂在一个叶子下，那么可以将叶子的数量减少 $1$，于是叶子最少的数量就是 $n-1-k-k = n-1-2k$；

如果根节点没有叶子节点，那么可移动芽的数量就变为 $k-1$，也就是只能减少 $k-1$ 个叶子，所以叶子最少的数量就是 $n-1-k-(k-1) = n-2k$；

代码实现

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
#include <bits/stdc++.h>
using namespace std;
	#define LL long long 
	#define ULL unsigned long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define B1 131
	#define B2 13331
	#define M1 1000000007
	#define M2 1000000009
	#define eps 1e-8
	#define MAXN 9e18
	#define MS 200009
	
int n,m,k;
vector<int > vc[MS];
int p[MS];
int cnt;

void dfs1(int u,int f){
	p[u] = 1;
	int cc = 0;
	for(auto v:vc[u]){
		if(v != f){
			dfs1(v,u);
			cc |= p[v];
		}
	}
	if(cc) p[u] = 0; 
	else p[u] = 1;
} 

void dfs2(int u, int f){
	for(auto v:vc[u]){
		if(v != f){
			cnt += !p[v];
			dfs2(v,u);
		}
	} 
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++) vc[i].clear();
	for(int i=2;i<=n;i++){
		int u,v; cin >> u >> v;
		vc[u].push_back(v);
		vc[v].push_back(u);
	}
	dfs1(1,1);
	int flag = 0;
	for(auto v:vc[1]){
		if(p[v]){
			flag = 1;
			break;
		}
	}
	cnt = 0;
	dfs2(1,1);
	//cout << "cnt = " << cnt << "\n";
	//cout << "flag = " << flag << "\n";
	cout << n-cnt*2-flag << "\n"; 
}

int main(){
	ios::sync_with_stdio(false);
	int ce = 1;
	cin >> ce;
	while(ce--){
		solve(); 
	} 
}
Prev
2021-09-17 16:30:00 # ACM
Next