| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 4156 | Accepted: 2512 |
Description
Input
Output
Sample Input
10 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10 3 8
Sample Output
3 8
题意：问删除哪些结点后，剩余各个子树的大小均小于总结点数目的一半。
树形DP的核心：将有向树当作无向树，从根节点结点遍历到叶子节点，从叶子节点回缩到根节点。
思路：一次DFS可求出每个结点的最大子树(不包含其本身)maxn以及子树之和sum(包含其本身),若(n-sum)<=n/2&&maxn<=n/2,则为答案。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int MAXN=10005; vector<int> tree[MAXN]; int n; int mx[MAXN]; int sum[MAXN]; void dfs(int u,int fa) { sum[u]=1; int maxn=0; int s=0; for(int i=0;i<tree[u].size();i++) { int v=tree[u][i]; if(v==fa) continue; dfs(v,u); s+=sum[v]; maxn=max(maxn,sum[v]); } mx[u]=maxn; sum[u]+=s; } int main() { while(scanf("%d",&n)!=EOF) { memset(sum,0,sizeof(sum)); memset(mx,0,sizeof(mx)); for(int i=1;i<=n;i++) tree[i].clear(); for(int i=1;i<=n-1;i++) { int u,v; scanf("%d%d",&u,&v); tree[u].push_back(v); tree[v].push_back(u); } dfs(1,-1); bool flag=false; for(int i=1;i<=n;i++) { if(max(n-sum[i],mx[i])<=n/2) { printf("%d\n",i); flag=true; } } if(!flag) printf("NONE\n"); } return 0; }
原文：http://www.cnblogs.com/program-ccc/p/5223745.html