55分 dfs+二叉树(捞)
查看原帖
55分 dfs+二叉树(捞)
723973
封禁用户楼主2022/5/15 20:29

45WA

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=140;
vector<int>a[maxn];
int n,m,x,y,cnt,sum,vis[maxn],val[maxn],dep[maxn],book[maxn];
void dfs(int num)
{
    int ans;
    book[num]=1;
    for(int i=0;i<a[num].size();++i)
    {
        ans=a[num][i];
        if(book[ans]==0)
        {
            vis[ans]=num;
            dep[ans]=dep[num]+1;
            cnt=max(cnt,dep[ans]);
            val[dep[ans]]++;
            dfs(ans);
        }
    }
    return;
}
int main()
{
    cin>>n;
    for(int i=1;i<n;++i)
    {
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    cin>>x>>y;
    dep[1]=1;
    dfs(1);
    for(int i=1;i<=n;++i)
    {
        m=max(m,val[i]);
    }
    if(dep[x]>dep[y])
    {
        swap(x,y);
    }
    while(dep[x]!=dep[y])
    {
        y=vis[y];
        sum+=2;
    }
    while(x!=y)
    {
        x=vis[x];
        y=vis[y];
        sum+=3;
    }
    cout<<cnt<<"\n"<<m<<"\n"<<sum;
    return 0;
}
2022/5/15 20:29
加载中...