本文轉(zhuǎn)載至：http://zhexue.sinaapp.com/?p=104
題目來(lái)源：POJ3107
給定一棵無(wú)根樹(shù)，刪除樹(shù)中一個(gè)節(jié)點(diǎn)，剩下各子樹(shù)的包含的節(jié)點(diǎn)數(shù)最大值最小，問(wèn)樹(shù)中有多少個(gè)這樣的節(jié)點(diǎn)?
解法：任意選擇一個(gè)節(jié)點(diǎn)，作為根，進(jìn)行遍歷。對(duì)一個(gè)節(jié)點(diǎn)V，設(shè)其子節(jié)點(diǎn)為cv[1..k]，f[v]為以節(jié)點(diǎn)v為根的子樹(shù)包含的節(jié)點(diǎn)數(shù)。
對(duì)于每一個(gè)節(jié)點(diǎn)V，刪除V之后剩下子樹(shù)含有的節(jié)點(diǎn)數(shù)中最大分別為 max{ f[cv[1]]，f[cv[2]]，....f[cv[k]]，SumNode-(f[cv[1]]+f[cv[2]]+....+f[cv[k]]) }，一次遍歷即可求出所有刪除一個(gè)節(jié)點(diǎn)后的最大子樹(shù)包含的節(jié)點(diǎn)數(shù)。
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
#define MAXN 50005
using namespace std;
vector<int>ansNode;
int maxNumNode;
int n, f[MAXN];
int pointTree[MAXN];
struct Tree{
int x,y;
}tree[MAXN*2];
int len;
bool cmp(struct Tree a, struct Tree b)
{
return a.x<b.x;
}
int treedp(int parentNode,int thisNode){
int maxNode=0;
int sumChildNode=0;
int index=pointTree[thisNode];
do{
int childNode=tree[index].y;
if(childNode != parentNode)
{
f[childNode]=treedp(thisNode,childNode);
sumChildNode+=f[childNode];
if(f[childNode]>maxNode)maxNode=f[childNode];
}
index++;
}while(index<len && tree[index].x==tree[index-1].x);
if(maxNode<n-sumChildNode-1)maxNode=n-sumChildNode-1;
if(maxNode<maxNumNode){
maxNumNode=maxNode;
ansNode.clear();
ansNode.push_back(thisNode);
}else if(maxNode==maxNumNode){
ansNode.push_back(thisNode);
}
return sumChildNode+1;
}
int main(int argc,int *argv[])
{
while(scanf("%d",&n)!=EOF){
len=0;
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
tree[len].x=x;
tree[len++].y=y;
tree[len].x=y;
tree[len++].y=x;
}
sort(tree,tree+len,cmp);
pointTree[tree[0].x]=0;
for(int i=1;i<len;i++){
if(tree[i].x != tree[i-1].x)
pointTree[tree[i].x] = i;
}
ansNode.clear();
maxNumNode=n;
treedp(-1,1);
sort(ansNode.begin(),ansNode.end());
for(int i=0;i<ansNode.size();i++)
printf("%d ",ansNode[i]);
}
return 0;
}