树形dp入门——poj2378

题目大意：给出一个大小为n的树，意欲破坏其中一个节点使得剩余残骸大小均不超过n/2，给出所有可行的节点编号（1~n）

思路很直接，拆除一个节点后，剩余部分为其若干儿子的子树以及该节点上层所连其余部分（n-size[i]），只要这些连接块大小都不超过n/2，该节点就满足条件。因而我们可以先求出每个节点所管辖的那棵树的大小，这里用到了dfs，也可以勉强算作dp：自下而上地为每个节点求出其子树规模（该点规模=其儿子的规模和+1）。

在建树的时候可以直接用连接表（vector）储存无向边，这时由于无法区分与每个点相连的是其父节点还是子节点，会引发问题：在dfs的时候把父节点误认作儿子节点，解决方法就是在递归的时候传入父节点编号，然后在递归，计算规模，比较残骸大小的时候避开它就可以了。

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;

int n;
int root;
vector<int>G[10000+400];
vector<int>ans;
int sz[10000+400];

void dfs(int par,int u){
    sz[u]=1;
    for(int i=0;i<(int)G[u].size();i++){
        if(G[u][i]!=par)
            dfs(u,G[u][i]);
    }
    int piece=0;
    for(int i=0;i<(int)G[u].size();i++)
        if(par!=G[u][i]){
            sz[u]+=sz[G[u][i]];
            piece=max(piece,sz[G[u][i]]);
        }
    piece=max(piece,n-sz[u]);
    if(piece<=n/2)
        ans.push_back(u);
}

int main(){
    while(cin>>n){
        memset(sz,0,sizeof(sz));
        int x,y;
        for(int i=0;i<n-1;i++){
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs(0,1);
        sort(ans.begin(),ans.end());
        for(int i=0;i<(int)ans.size();i++)
            cout<<ans[i]<<endl;
    }
    return 0;
}