大佬求助!!必关!!题目:P3884 [JLOI2009] 二叉树问题
  • 板块学术版
  • 楼主Ryan_L_F
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/29 17:20
  • 上次更新2024/12/29 21:24:21
查看原帖
大佬求助!!必关!!题目:P3884 [JLOI2009] 二叉树问题
1022974
Ryan_L_F楼主2024/12/29 17:20

大概是这样的,但第一个点爆了,求求看一看......

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, x, y, maxn;
struct stu{
    int f, l = 2e9, r = 2e9;
}ma[N];
int ceng[N], kuan[N], step[N];
void bfs(int id){
    memset(step, 0x3f, sizeof step);
    queue <int> q;
    step[id] = 0;
    q.push(id);
    while(q.size()){
        int x = q.front();
        q.pop();
        if(x == y){
            cout << step[x] << "\n";
            return ;
        }
        if(ma[x].l != 2e9 && step[ma[x].l] == 0x3f3f3f3f)
            q.push(ma[x].l), step[ma[x].l] = step[x] + 1;
        if(ma[x].r != 2e9 && step[ma[x].r] == 0x3f3f3f3f)
            q.push(ma[x].r), step[ma[x].r] = step[x] + 1;
        if(ma[x].f != 2e9 && step[ma[x].f] == 0x3f3f3f3f)
            q.push(ma[x].f), step[ma[x].f] = step[x] + 2;
    }
}

int main(){
    cin >> n;
    ceng[1] = 1;
    for(int i = 1; i < n; i++){
        int v, u;
        cin >> v >> u;
        if(ma[v].l == 2e9)
            ma[v].l = u, ceng[u] = ceng[v] + 1;
        else
            ma[v].r = u, ceng[u] = ceng[v] + 1;
        ma[u].f = v;
    }
    ma[1].f = 2e9;
    cin >> x >> y;
    for(int i = 1; i <= n; i++)
        maxn = max(maxn, ceng[i]), kuan[ceng[i]] ++;
    cout << maxn << "\n";
    int d = maxn;
    maxn = 1;
    for(int i = 1; i <= d; i++)
        maxn = max(maxn, kuan[i]);
    cout << maxn << "\n";
    bfs(x);
    return 0;
}
2024/12/29 17:20
加载中...