http://poj.org/problem?id=1655
Description
Consider a tree T with N (1 <= N <= 20,000) nodes numbered 1...N. Deleting any node from the tree yields a forest: a collection of one or more trees. Define the balance of a node to be the size of the largest tree in the forest T created by deleting that node from T.Output
For each test case, print a line containing two integers, the number of the node with minimum balance and the balance of that node.Sample Input
1 7 2 6 1 2 1 4 4 5 3 7 3 1
Sample Output
1 2
/** poj 1655 利用樹形dp求樹的重心 題目大意:求數的重心 解題思路:樹的重心定義為:找到一個點,其所有的子樹中最大的子樹節點數最少,那麼這個點就是這棵樹的重心,刪去重 心後,生成的多棵樹盡可能平衡. 實際上樹的重心在樹的點分治中有重要的作用, 可以避免N^2的極端復雜度(從退化鏈的一端出發),保證 NlogN的復雜度, 利用樹形dp可以很好地求樹的重心. */ #include#include #include #include using namespace std; const int maxn=20005; struct note { int v,next; }edge[maxn*2]; int head[maxn],ip; int maxx,point,n,num[maxn]; void init() { memset(head,-1,sizeof(head)); ip=0; } void addedge(int u,int v) { edge[ip].v=v,edge[ip].next=head[u],head[u]=ip++; } void dfs(int u,int pre) { int tmp=-0x3f3f3f3f; num[u]=1; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==pre)continue; dfs(v,u); num[u]+=num[v]; tmp=max(tmp,num[v]); } tmp=max(tmp,n-num[u]);///除去以u為根節點的子樹部分剩下的節點數 if(tmp