3. 找關鍵人物 [97全國賽]

頗單純的樹型DPˊˇˋ                                                                                                     .


寫得爛爛的orz

 應該是O(n^2)吧不會估XD

//************************

#include<stdio.h>
int n,a,b;
struct edge{
	int j;
	edge *next;
	void set(int jj,edge *n){
		j=jj;next=n;
	}
}E[40020],*V[20010];
int edgeCnt;
void set(int i,int j){
	//printf("set %d %d\n",i,j);
	edge *p=E+edgeCnt++,*q=E+edgeCnt++,*r;
	r=V[i];
	V[i]=p;
	p->set(j,r);
	r=V[j];
	V[j]=q;
	q->set(i,r);
}
int dp[20010],max[20010],son[20010];
int treedp(int now,int fa){
	//printf("treedp %d %d\n",now,fa);
	if(max[now])return son[now];
	int sub=0,tmp;
	for(edge *p=V[now];p;p=p->next){
		if(p->j == fa)continue;
		//printf("now %d now %d\n",now,p);
		sub++;
		son[now]+=treedp(p->j,now)+1;
		//printf("now %d son %d %d\n",now,p->j,son[p->j]);
		if(dp[now]<dp[p->j] || dp[now]==dp[p->j]&&max[now]>max[p->j]){
			dp[now]=dp[p->j];
			max[now]=max[p->j];
		}
	}
	if(sub==0){
		max[now]=-1;
		return son[now]=dp[now]=0;
	}
	tmp=son[now]*(n-son[now]-1);
	for(edge *p=V[now];p;p=p->next){
		if(p->j == fa)continue;
		for(edge *q=p;q;q=q->next){
			if(q->j == fa)continue;
			if(p->j!=q->j){
				tmp+=(1+son[p->j])*(1+son[q->j]);
			}
		}
	}
	if(tmp>dp[now] || tmp==dp[now]&&now<max[now]){
		max[now]=now;
		dp[now]=tmp;
	}
	return son[now];
}
main(){
	freopen("3.in","r",stdin);
	freopen("3.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		scanf("%d%d",&a,&b);
		set(a,b);
	}
	treedp(1,1);
	//for(int i=1;i<=n;i++)
	//	printf("node %d son %d dp %d max %d\n",i,son[i],dp[i],max[i]);
	printf("%d %d\n",max[1],dp[1]);
}