## 题目大意

### 举个栗子OwO

#### 样例输入

``````1
7
2 6
1 2
1 4
4 5
3 7
3 1
``````

#### 样例输出

``````1 2
``````

#### 来自

POJ Monthly–2004.05.15 IOI 2003 sample task

### 思路

``````void dfs(int now){
/*发现时间*/
if(条件){}
for(i in son[now]){
if(条件){
dfs(i);
/*回溯*/
}
}
/*离开时间*/
}
``````

`d[now]+=d[G[now][i]];`

``````/*O(N)算法*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#define N 20000+5
#define INF 2147483646
using namespace std;

int T,n,a,b,vis[N],d[N],t[N];
vector<int>G[N];

void dfs(int now,int fa){
if(G[now].size()==0) return;
int max_t=-1;
for(int i=0;i<G[now].size();i++)
if(!vis[G[now][i]]){
vis[G[now][i]]=1;
dfs(G[now][i],now);
d[now]+=d[G[now][i]];
if(max_t<d[G[now][i]]) max_t=d[G[now][i]];
}
t[now]=max(max_t,n-d[now]);
}

int main(){
cin>>T;
while(T--){
cin>>n;
for(int i=0;i<=N;i++) d[i]=1;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1;i<n;i++){
cin>>a>>b;
}
vis[1]=1;
dfs(1,0);
int min_t=INF-1,node;
for(int i=1;i<=n;i++){
if(min_t>t[i]){min_t=t[i];node=i;}
}
cout<<node<<" "<<min_t<<endl;
}
return 0;
}
``````

This site uses Akismet to reduce spam. Learn how your comment data is processed.