LCA死循环求猪选官
查看原帖
LCA死循环求猪选官
772815
一咕咕一楼主2024/10/9 23:11

诊断问题:出现在LCA中!

#include <bits/stdc++.h>
using namespace std;
vector<int> tr[107];
int n;
int deep[107], countdeep[107], father[107], visited[107];
int Deep, Width;
void DFS(int d, int rt)
{
    if(visited[rt])
        return;
    visited[rt] = true;
    deep[rt] = d;
    countdeep[d]++;
    Deep = max(Deep, d);
    Width = max(Width, countdeep[d]);
    for (auto x : tr[rt])
        father[x] = rt, DFS(d + 1, x);
}
int LCA(int x, int y)
{
    while (x != y)
    {
        // cout << x << ' ' << y << endl;
        if (deep[x] < deep[y])
            y = father[y];
        else
            x = father[x];
    }
    return x;
}
int main()
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    int x, y;
    cin >> x >> y;
    DFS(1, 1);
    int lca = LCA(x, y);
    cout << Deep << '\n'
         << Width << '\n'
         << deep[x] - deep[lca] + (deep[y] - deep[lca]) * 2;
    // putchar('\n'), system("pause");
    return 0;
}
2024/10/9 23:11
加载中...