第一次dfs求出每個子樹的節點數
第二次dfs求答案
這一題是poj1741的基礎
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int N;
vector<int>son[20010]; //圖的存儲結構
int vis[20010]; //標記是否訪問過
int num[20010]; //子樹節點的數量
int dp[20010]; //答案
void dfs_num(int n){
int len=son[n].size();
num[n]=1;
vis[n]=1;
for(int i=0;i<len;i++){
int k=son[n][i]; //兒子
if(vis[k]) continue;
dfs_num(k);
num[n]+=num[k];
}
// printf("@ %d %d\n",n,num[n]);
}
void dfs_node(int n,int from){
int k,len=son[n].size();
vis[n]=1;
dp[n]=0;
for(int i=0;i<len;i++){
k=son[n][i];
if(vis[k]){
dp[n]=max(dp[n],N-num[n]);
}
else{
dp[n]=max(dp[n],num[k]);
dfs_node(k,n);
}
}
}
int main()
{
int i,j,k,T,u,v;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(i=1;i<=N;i++) son[i].clear();
memset(num,0,sizeof(num));
memset(dp,0,sizeof(dp));
for(i=1;i<=N-1;i++) {
scanf("%d%d",&u,&v);
son[u].push_back(v);
son[v].push_back(u);
}
memset(vis,0,sizeof(vis)); dfs_num(1);
memset(vis,0,sizeof(vis)); dfs_node(1,-1);
for(i=j=k=N;i>=1;i--){
if(k>dp[i]){
k=dp[i];
j=i;
}
if(k==dp[i]){
j=i;
}
}
printf("%d %d\n",j,k);
}
return 0;
}
/*
2
7
2 6
1 2
1 4
4 5
3 7
3 1
11
1 2
1 3
1 4
2 5
2 6
4 7
4 8
4 9
8 10
8 11
*/
