直径求调
查看原帖
直径求调
324412
Filberte楼主2023/12/29 11:17

能过样例,交上去全错。且错误都在第二行。

#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
using namespace std;
const int N = 2e5 + 100;
int n;
int h[N], idx = 1;
int ver[N << 1], nxt[N << 1];
ll w[N << 1];
void add(int u, int v, ll c){
    ver[++idx] = v;
    nxt[idx] = h[u];
    w[idx] = c;
    h[u] = idx;
    ver[++idx] = u;
    nxt[idx] = h[v];
    w[idx] = c;
    h[v] = idx;
}
int a, b;
ll dis[N];
int fr[N], to[N];
bool ban[N];
void dfs(int u, int fa){
    for(int i = h[u];i;i = nxt[i]){
        int v = ver[i];
        if(v == fa) continue;
        dis[v] = dis[u] + w[i];
        fr[v] = u;
        dfs(v, u);
    }
}
vector<int> d;
ll ex[N];
void dfs2(int u, int fa){
    for(int i = h[u];i;i = nxt[i]){
        int v = ver[i];
        if(v == fa || ban[v]) continue;
        dfs2(v, u);
        ex[u] = max(ex[u], ex[v] + w[i]);
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1, u, v;i < n;i++){
        ll c;
        scanf("%d%d%lld",&u,&v,&c);
        add(u, v, c);  
    }
    dfs(1, 1);
    for(int i = 1;i <= n;i++) if(dis[i] >= dis[a]) a = i;
    dis[a] = 0;fr[a] = -1;
    dfs(a, a);
    for(int i = 1;i <= n;i++) if(dis[i] >= dis[b] && i != a) b = i;
    printf("%lld\n",dis[b]);
    to[b] = -1;
    for(int x = b;;x = fr[x]){
        ban[x] = 1;
        if(fr[x] != -1) to[fr[x]] = x;
        else break;
    }
    // cout << a << " " << b << "\n";
    // for(int i = 1;i <= n;i++) cout << fr[i] << " ";
    // cout << "\n";
    // for(int i = 1;i <= n;i++) cout << to[i] << " ";
    // cout << "\n";
    int l, r;
    for(int i = a;i != -1;i = to[i]){
        dfs2(i, i);
        if(dis[b] - dis[i] <= ex[i]){r = i;break;}
    }
    for(int i = b;i != -1;i = fr[i]){
        dfs2(i, i);
        if(dis[i] <= ex[i]){l = i;break;}
    }
    printf("%d\n",r - l + 1);
    return 0;
}
2023/12/29 11:17
加载中...