社区讨论

1,9,10WA,求助

P3884[JLOI2009] 二叉树问题参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo1zak5s
此快照首次捕获于
2023/10/23 05:26
2 年前
此快照最后确认于
2023/11/03 05:50
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;

struct node{
    int father;int left;int right;int deep;
};

node f[110];

int n;
int a,b,c,d,pd = 0;
int res = 0,idx = 1;
int ans1,ans2,ans3;
int tong[110],vis[110] = {0};

void dfs(int root,int dp) {
    if(root == 0) return;

    f[root].deep = dp;
    tong[dp]++;
    dfs(f[root].left,dp + 1);
    dfs(f[root].right,dp + 1);
}

void getDis(int st,int ed,int dis) {
    if(st == 0 || vis[st]) return;
    if(st == ed) {pd = 1; ans3 = dis; return;}
    vis[st] = 1;
    if(!pd) {
        getDis(f[st].left,ed,dis + 1);
        getDis(f[st].right,ed,dis + 1);
        getDis(f[st].father,ed,dis + 1);   
    }
}
int main(){
    cin >> n;
    for(int i = 1;i < n;i++) {
        cin >> a >> b;
        if(f[a].left == 0) f[a].left = b;
        else f[a].right = b;

        f[b].father = a;
    }

    dfs(1,1);

    for(int i = 1;i <= n;i++) {
        ans1 = max(ans1,f[i].deep);
        ans2 = max(ans2,tong[i]);
    }

    cin >> c >> d;


    getDis(c,1,0); 
    res += ans3 * 2;
    pd = 0;

    getDis(1,d,0);
    res += ans3;

    cout << ans1 << '\n' << ans2 << '\n' << res << endl;
    
    

    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...