73分求助!!!
查看原帖
73分求助!!!
757625
Christins楼主2023/10/27 17:43
#include <bits/stdc++.h> 

using i64 = long long;
const int N = 110;
std::vector<int> adj[N];
int n, y, x;
int dep, wid = 1, ans;
std::vector<int> st(110);
const int INF = 0x3f3f3f3f;

void dfs(int u, int fa, int de)
{
    dep = std::max(de, dep);

    for (int x : adj[u]) {
        if (x == fa) continue;
        dfs(x, u, de + 1);
    }
}

void bfs(int u)
{
    std::queue<int> q;
    q.push(u);
    st[u] = true;
    
    while (q.size()) {
        int t = q.front();
        q.pop();

        for (int x : adj[t]) {
            if (x == t || st[x]) continue;
            q.push(x);
            st[x] = true;
        }
        wid = std::max(wid, (int)q.size());
    }
}

std::vector<int> dist(110, INF);
int serach(int u) {
    st.assign(110, 0);
    std::queue<int> q;
    q.push(u);
    st[u] = true;

    dist[u] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop();

        for (auto f : adj[t]) {
            if (f == t || st[f]) continue;
            if (dist[f] > dist[t] + 1) {
                dist[f] = dist[t] + 1;
                st[f] = true;
                q.push(f);
            }
        }
    }

    return dist[y] + 2 * dist[x];
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cin >> n;
    n -= 1;

    while (n--) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs(1);
    dfs(1, 0, 1);

    std::cin >> x >> y;

    ans = serach(1);

    std::cout << dep << '\n' << wid << '\n' << ans << '\n';

    return 0;
}
2023/10/27 17:43
加载中...