@[Coast233](/user/539726) 我觉得
1. 这是无向图。
2. 递归爆栈了？？？
by Adchory @ 2023-01-07 19:58:54
@[初雪_matt](/user/360083) 万分感谢，我改对了。当时我是把坐标小做爸爸，所以没有标记，忘了```cpp
1-3
2-3
```
的情况。
by Xeffry @ 2023-01-07 20:00:14
@[Coast233](/user/539726) 没事
by 初雪_matt @ 2023-01-07 20:00:51
@[Reimu_Hakurei](/user/590600) 没有爆，我当时觉得1和3有路
就可以记为1是3的根，但是我没有想到如果又有2和3，那么就只有2通向3的路，没有3通向2的路。我是想得优化成单向图。这是我改了以后的代码```cpp
#include<bits/stdc++.h>
using namespace std;
struct vla{
vector<int>next;
int son,ans;
}pop[50003];
int n,ans=INT_MAX,ansx=1,bok[50003],book[50003];
void dfs(int x,int dep){
bok[x]=1;
pop[x].ans=dep;
pop[x].son=1;
for(int i=0;i<pop[x].next.size();i++){
if(!bok[pop[x].next[i]]){
dfs(pop[x].next[i],dep+1);
pop[x].ans+=pop[pop[x].next[i]].ans;
pop[x].son+=pop[pop[x].next[i]].son;
}
}
}
void dff(int x,int last){
book[x]=1;
if(x!=1){
last+=n-2*pop[x].son;
pop[x].ans=last;
}
for(int i=0;i<pop[x].next.size();i++){
if(!book[pop[x].next[i]]){
dff(pop[x].next[i],last);
}
}
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
pop[x].next.push_back(y);
pop[y].next.push_back(x);
}
dfs(1,0);
dff(1,pop[1].ans);
for(int i=1;i<=n;i++){
if(ans>pop[i].ans){
ans=pop[i].ans;
ansx=i;
}
}
cout<<ansx<<" "<<ans;
return 0;
}
```
by Xeffry @ 2023-01-07 20:06:40
```cpp
#include<bits/stdc++.h>
using namespace std;
struct vla{
vector<int>next;
int son,ans;
}pop[50003];
int n,ans=INT_MAX,ansx=1,bok[50003],book[50003];
void dfs(int x,int dep){
bok[x]=1;
pop[x].ans=dep;
pop[x].son=1;
for(int i=0;i<pop[x].next.size();i++){
if(!bok[pop[x].next[i]]){
dfs(pop[x].next[i],dep+1);
pop[x].ans+=pop[pop[x].next[i]].ans;
pop[x].son+=pop[pop[x].next[i]].son;
}
}
}
void dff(int x,int last){
book[x]=1;
if(x!=1){
last+=n-2*pop[x].son;
pop[x].ans=last;
}
for(int i=0;i<pop[x].next.size();i++){
if(!book[pop[x].next[i]]){
dff(pop[x].next[i],last);
}
}
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
pop[x].next.push_back(y);
pop[y].next.push_back(x);
}
dfs(1,0);
dff(1,pop[1].ans);
for(int i=1;i<=n;i++){
if(ans>pop[i].ans){
ans=pop[i].ans;
ansx=i;
}
}
cout<<ansx<<" "<<ans;
return 0;
}
```
by Xeffry @ 2023-01-07 20:07:10