#include <bits/stdc++.h>
using namespace std;
const int maxn = 500+5;
int head[maxn];
int cs[maxn];
int deep[maxn];
int d[maxn];
int k = 0;
int dmaxn = -1;
int wmaxn = -1;
int lcc[maxn][21];
struct note{
int v;
int next;
}e[maxn*2];
void add(int u,int v){
e[k].v = v;
e[k].next = head[u];
head[u] = k++;
}
void dfs(int u,int fa){
d[u] = d[fa]+1;
dmaxn = max(dmaxn,d[u]);
lcc[u][0] = fa;
for(int i = 1;d[u]>=(1<<i);i++)
lcc[u][i] = lcc[lcc[u][i-1]][i-1];
for(int i = head[u];i!=-1;i = e[i].next){
int v = e[i].v;
if(v!=fa){
dfs(v,u);
}
}
}
int lca(int a,int b){
int ans = 0;
if(d[b]>d[a]){
for(int i = 20;i>=0;i--){
if(d[a]<=d[b]-(1<<i)){
b = lcc[b][i];
ans+=(1<<i);
}
}
if(a == b){
return ans;
}
for(int i = 20;i>=0;i--){
if(lcc[a][i] == lcc[b][i]){
continue;
}
else{
a = lcc[a][i];
b = lcc[b][i];
if(i == 0){
ans+=3;
}
else{
ans+=3*(1<<i);
}
}
}
}
else if(d[a]>d[b]){
for(int i = 20;i>=0;i--){
if(d[b]<=(d[a]-(i<<1))){
a = lcc[a][i];
ans+=2*(1<<i);
}
}
if(a == b){
return ans;
}
for(int i = 20;i>=0;i--){
if(lcc[a][i] == lcc[b][i]){
continue;
}
else{
a = lcc[a][i];
b = lcc[b][i];
if(i == 0){
ans+=3;
}
else{
ans+=3*(1<<i);
}
}
}
}
else{
if(a == b){
return ans;
}
for(int i = 20;i>=0;i--){
if(lcc[a][i] == lcc[b][i]){
continue;
}
else{
a = lcc[a][i];
b = lcc[b][i];
if(i == 0){
ans+=3;
}
else{
ans+=3*(1<<i);
}
}
}
}
return ans+3;
}
int n;
int main(){
memset(head,-1,sizeof(head));
cin>>n;
for(int i = 1;i<n;i++){
int t1,t2;
scanf("%d%d",&t1,&t2);
add(t1,t2);
add(t2,t1);
}
int t1,t2;
dfs(1,0);
scanf("%d%d",&t1,&t2);
for(int i = 1;i<=n;i++){
cs[d[i]]++;
}
for(int i = 1;i<=dmaxn;i++){
wmaxn = max(wmaxn,cs[i]);
}
cout<<dmaxn<<endl<<wmaxn<<endl;
cout<<lca(t1,t2);
return 0;
}
求dalao们帮我看看,哪里出了问题
70分,#1,#6,#9出了问题