題目大意：給定一棵n棵節點的樹，如果刪去某個節點使得剩下來的最大分支節點數小等於節點總數的一半則這個刪除就是叼爆的，問叼爆的刪法總數。
解題思路：樹形DP.深搜兩次，第一次深搜記錄從當前節點的子孫節點總數（包括自己）,第一次算預處理，復雜度為O(N),第二次利用第一次的結果找各分支的最大節點數，分支有兩種情況，一種是孩子的分支，一種當前節點到父親節點的那條分支（總數為N-dp[cur])，這樣再算N次即可得解。
測試數據：
10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8
代碼：
[html]
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 110000
#define max(a,b) (a)>(b)?(a):(b)
struct node {
int v;
node *next;
}*head[MAX],tree[MAX];
int n,m,ptr,dp[MAX],ans[MAX],cnt;
void Initial() {
cnt = ptr = 0;
memset(dp,0,sizeof(dp));
memset(head,NULL,sizeof(head));
}
void AddEdge(int x,int y) {
tree[ptr].v = y;
tree[ptr].next = head[x],head[x] = &tree[ptr++];
tree[ptr].v = x;
tree[ptr].next = head[y],head[y] = &tree[ptr++];
}
void Dfs_Ini(int s,int pa) {
dp[s] = 1;
node *p = head[s];
while (p != NULL) {
if (p->v != pa) {
Dfs_Ini(p->v,s);
dp[s] += dp[p->v];
}
p = p->next;
}
}
void Dfs_Solve(int son,int pa) {
int i,j,tp,tot = 0;
node *p = head[son];
while (p != NULL) {
if (p->v != pa) {
Dfs_Solve(p->v,son);
tp = dp[p->v];
tot = max(tot,tp);
}
p = p->next;
}
if (n - dp[son] <= n / 2 && tot <= n / 2)
cnt++,ans[cnt] = son;
}
int main()
{
int i,j,k,a,b;
while (scanf("%d",&n) != EOF) {
Initial();
for (i = 1; i < n; ++i) {
scanf("%d%d",&a,&b);
AddEdge(a,b);
}
Dfs_Ini(1,0); //第一次深搜，記錄當前節點的子孫總數
Dfs_Solve(1,0); //更新答案
sort(ans+1,ans+1+cnt); //按字典序輸出
for (i = 1; i <= cnt; ++i)
printf("%d\n",ans[i]);
if (cnt == 0) printf("NONE\n");
}
}
