代码求调,只过了前4个点,有没有大佬看看
查看原帖
代码求调,只过了前4个点,有没有大佬看看
1103407
climber0楼主2024/7/15 11:20
#include<bits/stdc++.h>
#define long long int
#define nn '\n'
using namespace std;

const int maxn = 2e6 + 5;
vector<pair<int, int>> e[maxn];
int d[maxn], l, r;
int pre[maxn];
int a[maxn], cnt;
int dp[maxn];
int dr[maxn]; // 到r的距离
bitset<maxn> dia; // 是否在直径上

void dfs(int u, int fa) {
    for(auto ed: e[u]) {
        int v = ed.first, w = ed.second;
        if(v == fa) continue;
        d[v] = d[u] + w;
        if(d[v] > d[l]) l = v;
        dfs(v, u);
    }
}
void dfspre(int u, int fa) {
    for(auto ed: e[u]) {
        int v = ed.first, w = ed.second;
        if(v == fa) continue;
        d[v] = d[u] + w;
        pre[v] = u;
        if(d[v] > d[r]) r = v;
        dfspre(v, u);
    }
}
void dpdfs(int u, int fa) {
    dp[u] = 0;
    for(auto ed: e[u]) {
        int v = ed.first, w = ed.second;
        if(v == fa || dia[v]) continue;
        dpdfs(v, u);
        dp[u] = max(dp[u], dp[v] + w);
    }
}
void solve() {
    int n, u, v, w;
    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    dfs(1, 0);
    r = l;
    d[r] = 0;
    dfspre(r, 0);
    cout << d[r] << nn;
    for(int u = r; ; u = pre[u]) {
        a[++cnt] = u;
        dia[u] = 1;
        if(u == l) break;
    }
    map<pair<int, int>, int> m;
    for(int i = 1; i <= cnt - 1; i++) {
        int u = a[i];
        for(auto ed: e[u]) {
            int v = ed.first, w = ed.second;
            if(v == a[i + 1]) {
                m[{u, v}] = m[{v, u}] = w;
                break;
            }
        }
    }
    for(int i = 2; i <= cnt; i++) {
        dr[a[i]] = dr[a[i - 1]] + m[{a[i], a[i - 1]}];
    }
    int ll, rr;
    for(int i = 1; i <= cnt; i++) {
        dpdfs(a[i], 0);
        if(dp[a[i]] == dr[l] - dr[a[i]]) {
            rr = i;
            break;
        }
    }
    for(int i = rr; i >= 1; i--) {
        dpdfs(a[i], 0);
        if(dp[a[i]] == dr[a[i]]) {
            ll = i;
            break;
        }
    }
    // cout << rr << ' ' << ll << nn;
    cout << abs(rr - ll) << nn;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    // cin >> _;
    while(_--)
        solve();
    return 0;
}
2024/7/15 11:20
加载中...