#1一直WA,求大佬协助
查看原帖
#1一直WA,求大佬协助
1116801
black_cat666楼主2024/3/24 15:47
#include <iostream>
#include <map>
#include <set>
#include <cstring>
#include <queue>
#include <vector>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 110;

struct node{
    int w;
    int l; //该节点的左节点
    int r; //该节点的右节点
    int t1; //该节点的根节点'
    int h; //该节点深度
}s[N];
int d[N][N]; //节点i到j的距离
bool st[N]; //节点是否走过
int w1[N]; //宽度

void bfs(int x){
    queue<int>q;
    q.push(x);
    st[x] = true;
    d[x][x] = 0;
    while(!q.empty()){
        int t = q.front();
        q.pop();
        //走左边
        if(s[t].l != 0 && !st[s[t].l]){
            d[x][s[t].l] = d[x][t] + 1;
            q.push(s[t].l);
            st[s[t].l] = true;
        }
        //走右边
        if(s[t].r != 0 && !st[s[t].r]){
            d[x][s[t].r] = d[x][t] + 1;
            q.push(s[t].r);
            st[s[t].r] = true;
        }
        //走根
        if(s[t].t1 != 0 && !st[s[t].t1]){
            d[x][s[t].t1] = d[x][t] + 2;
            q.push(s[t].t1);
            st[s[t].t1] = true;
        }
    }
}

int main(){
    int n;
    cin >> n;
    s[1].h = 1;
    for(int i = 1;i <= n - 1;i++){
        int a,b;
        cin >> a >> b;
        if(s[a].l != 0 && s[a].r != 0)continue;
        if(s[b].t1 != 0)continue;
        if(s[a].l == 0){
            s[a].l = b;
        }else{
            s[a].r = b;
        }
        s[b].h = s[a].h + 1;
        s[b].t1 = a;
    }
    for(int i = 1;i <= n;i++){
        memset(st,0,sizeof st);
        bfs(i);
    }
    //求深度
    int maxh = 0;
    for(int i = 1;i <= n;i++){
        maxh = max(s[i].h,maxh);
    }
    //求宽度(到根节点距离相同的最大值)
    int maxw = 0;
    for(int i = 2;i <= n;i++){
        w1[d[i][1]]++;
        maxw = max(maxw,w1[d[i][1]]);
    }
    int x,y;
    cin >> x >> y;
    cout << maxh << endl << maxw << endl << d[x][y];
}
2024/3/24 15:47
加载中...