Submission #1289239

#TimeUsernameProblemLanguageResultExecution timeMemory
1289239ar_tkinterPaths (RMI21_paths)C++20
12 / 100
47 ms13960 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct E { int v; ll w; };
const int N = 100000;
int n,k;
vector<E> g[N+1];
ll dn[N+1], up[N+1], a1[N+1], a2[N+1];
int ch[N+1];

void f1(int u,int p){
    a1[u]=a2[u]=0;
    for(auto [v,w]:g[u]) if(v!=p){
        f1(v,u);
        ll x=dn[v]+w;
        if(x>a1[u]){a2[u]=a1[u];a1[u]=x;ch[u]=v;}
        else if(x>a2[u]) a2[u]=x;
    }
    dn[u]=a1[u];
}
void f2(int u,int p){
    for(auto [v,w]:g[u]) if(v!=p){
        ll y=(ch[u]==v?a2[u]:a1[u]);
        up[v]=max(up[u],y)+w;
        f2(v,u);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    for(int i=0;i<n-1;i++){
        int a,b; ll w;
        cin>>a>>b>>w;
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }
    f1(1,0);
    up[1]=0;
    f2(1,0);
    for(int i=1;i<=n;i++)
        cout<<max(dn[i],up[i])<<(i==n?'\n':' ');
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...