真是佛了,不知道为什么,注释都写上了
#include<bits/stdc++.h>
#include<list>
#include<string.h>//其实只用了strlen()
using namespace std;
list<int> l;//可以用deque
int n,x,y;
struct Node{
int p,s1=0,s2=0;
}tree[10005];
int dist(){//求距离
if(x==1){//特殊判断
int num=0;
int yy=y;
while(yy!=1){
yy=tree[yy].p;
num++;
}
return num;
}
if(y==1){//特殊判断
int num=0;
int xx=x;
while(xx!=1){
xx=tree[xx].p;
num+=2;
}
return num;
}
int j[n+5],k[n+5],numj=0,numk=0;//用两个数组把x和y的祖先全存下来
int xx=x,yy=y;
while(xx!=1){//存入
xx=tree[xx].p;
j[++numj]=xx;
}
while(yy!=1){//存入
yy=tree[yy].p;
k[++numk]=yy;
}
for(int i=1;i<=numj;i++){//搜索并计算
for(int l=1;l<=numk;l++){
if(j[i]==k[l]) return 2*i+l;
}
}
}
void insertx(int a,int b){
/*
插入
第一个数是第二个数的父亲
虽然没有说
但本题不用考虑b是a的父亲
否则会MLE和TLE
*/
if(tree[a].s1==0) tree[a].s1=b;
else tree[a].s2=b;
tree[b].p=a;
}
int deep(int x){//向根节点递归
return(x==1)?1:deep(tree[x].p)+1;
}
int wide(int m){//m为要查找的层数
l.clear();
l.push_front(1);//l存这一层有那些数
for(int i=1;i<=m;i++){//循环m次,到m层
list<int> q;//其实是想写一个queue,但是后面要把l变成q(可以用deque)
while(!l.empty()){//把当前层每一个数的子节点放进去
int k=l.front();
if(tree[k].s1) q.push_back(tree[k].s1);
if(tree[k].s2) q.push_back(tree[k].s2);
l.pop_front();
}
l.clear();l=q;
}
return l.size();//最后输出l中元素的个数,个数就是宽度
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int a,b;scanf("%d%d",&a,&b);
insertx(a,b);
}scanf("%d%d",&x,&y);
int dep=1;//逐一查看深度,保留最大的深度
for(int i=2;i<=n;i++){
if(deep(i)>dep) dep=deep(i);
}
cout<<dep<<endl;
int wid=1;//逐一查看宽度,保留最大的宽度,循环次数是深度
for(int i=1;i<=dep;i++){
if(wide(i)>wid) wid=wide(i);
}
cout<<wid<<endl;
cout<<dist();
}