（樹形dp）poj 2378 Tree Cutting

題目

poj2378

題意：

有一棵樹，以某個結點為根并切斷這個結點使得它下一層所有的子樹的連通度 ≤ n / 2，如果有這樣的結點則輸出結點的編号。

思路：

以結點1為根，記錄每個結點向下的連通度（向上的連通度 = n - 向下的連通度）。

對于其中一個結點 p ，周遊與它有邊的結點s1，s2，，，sn，

如果結點 si 的向下的連通度 < 結點 p 向下的連通度，那麼這個結點 si 是結點 p 的子樹，那麼這個結點 si 在删除結點 p 後的連通度 = 這個結點 si 的向下的連通度。

如果結點 si 的向下的連通度 > 結點 p 向下的連通度，那麼這個結點 si 是結點 p 的parent，那麼這個結點 si 在删除結點 p 後的連通度 = n - 這個結點 si 的向下的連通度。

代碼

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector> 
#define DEBUG freopen("_in.txt", "r", stdin); freopen("_out1.txt", "w", stdout);
using namespace std;
const int MAXN = 1e4 + 10;
int dp[MAXN];
bool vis[MAXN];
vector<int> tree[MAXN];
void dfs(int p){
	vis[p] = true;
	int len = tree[p].size();
	dp[p] = 0;
	for (int i = 0, s, v; i < len; i++){
		s = tree[p][i];
		if (!vis[s]){
			dfs(s);
			dp[p] = dp[p] + dp[s] + 1;   //計算p的向下的連通度
		}
	}
}
int main(){
	int n;
	scanf("%d", &n);
	for (int i = 1, p, s; i < n; i++){
		scanf("%d%d", &p, &s);
		tree[p].push_back(s);
		tree[s].push_back(p);
	}
	dfs(1);
	int limit = n >> 1;
	bool ac;
	for (int i = 1; i <= n; i++){
		int len = tree[i].size();
		ac = true;
		for (int j = 0, s; j < len; j++){
			s = tree[i][j];
			if (dp[s] < dp[i] && dp[s] + 1 > limit){  //s是i的子樹
				ac = false;
				break;
			}
			else if (dp[s] > dp[i] && n - dp[i] - 1 > limit){  //s是i的parent
				ac = false;
				break;
			}
		}
		if (ac)
			printf("%d\n", i);
	}
	return 0;
}