50分求助!
查看原帖
50分求助!
110319
LYR_楼主2021/9/12 15:54
#include <bits/stdc++.h>
#define P pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>

using namespace std;
typedef long long ll;
const int N = 110;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
int n, d[N], w[N], f[N][10];
vector<int> G[N];
void dfs(int u) {
    d[u] = d[f[u][0]] + 1;
    w[d[u]]++;
    for (auto v : G[u]) {
        if (v == f[u][0]) continue;
        f[v][0] = u;
        dfs(v);
    }
}
void init() {
    for (int j = 1; j <= 7; j++) {
        for (int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
}
int lca(int x, int y) {
    if (d[x] < d[y]) swap(x, y);
    for (int j = 7; j >= 0; j--) {
        if (d[f[x][j]] >= d[y]) x = f[x][j];
    }
    if (x == y) return x;
    for (int j = 7; j >= 0; j--) {
        if (f[x][j] != f[y][j]) {
            x = f[x][j];
            y = f[y][j];
        }
    }
    return f[x][0];
}
int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    int s, t;
    cin >> s >> t;
    dfs(1);
    int depth, width;
    depth = width = 0;
    for (int i = 1; i <= n; i++) {
        depth = max(depth, d[i]);
        width = max(width, w[i]);
    }
    cout << depth << "\n" << width << "\n";
    int LCA = lca(s, t);
    cout << 2 * (d[s] - d[LCA]) + d[t] - d[LCA] << "\n";
    return 0;
}

LCA做法,大佬们帮忙看看,谢谢

2021/9/12 15:54
加载中...