91分#1WA求助! 调半天了
查看原帖
91分#1WA求助! 调半天了
782500
Hojstyer楼主2023/2/7 22:13
#include<bits/stdc++.h>
using namespace std;

int n,xi,yi,wide[110],maxw,maxd,ans,use[110],x[110],y[110],cnt;
struct tree
{
    int left,right,deep,father;
}t[110];

void dfs(int root)      //dfs求各个结点的深度 和各个深度的结点个数(深度)
{
    if(t[root].left)
    {
        t[t[root].left].deep=t[root].deep+1;
        wide[t[t[root].left].deep]++;
        dfs(t[root].left);
    }
    if(t[root].right)
    {
        t[t[root].right].deep=t[root].deep+1;
        wide[t[t[root].right].deep]++;
        dfs(t[root].right);
    }
    if(!t[root].left && !t[root].right) maxd=max(maxd,t[root].deep);
}

int lca(int a,int b)   //这里求的是结点a到a,b这两个结点到最近公共祖先的距离
{
    if(!t[a].father) return 0;
    if(t[a].father==t[b].father) return 1;
    if(t[a].deep<t[b].deep) return lca(a,t[b].father);
    return lca(t[a].father,b)+1;
}

int main()
{
    t[1].deep=1;
    wide[t[1].deep]++;
    use[1]=1;  //use数组记录该节点是否被填入(既是否能作为局部跟结点)
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>x[i]>>y[i];
    }
    while(cnt!=n-1)      //由于不清楚x,y哪个是父,哪个是子 故判断填入
    {
        for(int i=1;i<n;i++)
        {
            if(!x[i] && !y[i]) continue;
            if(use[x[i]] && !use[y[i]])  //如果一个可以作为根结点 一个并未填入
            {
                if(!t[x[i]].left) t[x[i]].left=y[i];
                else t[x[i]].right=y[i];
                t[y[i]].father=x[i];
                use[y[i]]=1,x[i]=0,y[i]=0;
                cnt++;
                break;
            }
            else if(use[y[i]] && !use[x[i]])
            {
                if(!t[y[i]].left) t[y[i]].left=x[i];
                else t[y[i]].right=x[i];
                t[x[i]].father=y[i];
                use[x[i]]=1,x[i]=0,y[i]=0;
                cnt++;
                break;
            }
        }
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        maxw=max(maxw,wide[i]);
    }
    cin>>xi>>yi;
    ans=2*lca(xi,yi)+lca(yi,xi);
    cout<<maxd<<'\n'<<maxw<<'\n'<<ans<<'\n';
    system("pause");
    return 0;
}
2023/2/7 22:13
加载中...