C++(g++ 7.5.0) 解法, 执行用时: 10ms, 内存消耗: 2184K, 提交时间: 2022-09-15 16:31:17

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using PII = pair<int, int>;

void solve(int n) {
    vector<vector<PII>> e(n);
    for (int u = 1; u < n; u++) {
        int v, w;
        cin >> v >> w;
        v--;
        e[v].push_back({u, w});
        e[u].push_back({v, w});
    }
    function<void(int, int, vector<int> &)> dfs = [&](int u, int father, vector<int> &d) {
        for (auto [v, w] : e[u]) if (v != father) {
            d[v] = d[u] + w;
            dfs(v, u, d);
        }
    };
    vector<int> d(n);
    dfs(0, 0, d);
    int ep1 = max_element(d.begin(), d.end()) - d.begin();
    vector<int> d1(n), d2(n);
    dfs(ep1, ep1, d1);
    int ep2 = max_element(d1.begin(), d1.end()) - d1.begin();
    dfs(ep2, ep2, d2);
    for (int i = 0; i < n; i++) {
        cout << max(d1[i], d2[i]) << '\n';
    }
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    while (cin >> n) {
        solve(n);
    }
    return 0;
}

C++ 解法, 执行用时: 8ms, 内存消耗: 1944K, 提交时间: 2022-02-09 14:57:54

#include<bits/stdc++.h>
using namespace std;
int n,cnt,hd[50005],vt[50005],nt[50005],cs[50005],d1[50005],d2[50005],s[50005],ans[50005],x,y;
void add(int x,int y,int w){nt[++cnt]=hd[x];hd[x]=cnt;vt[cnt]=y;cs[cnt]=w;}
void it(int x,int fa){
	for(int i=hd[x];i;i=nt[i]){
		int v=vt[i];
		if(v==fa)continue;
		it(v,x);
		if(d1[v]+cs[i]>d1[x])d2[x]=d1[x],d1[x]=d1[v]+cs[i],s[x]=v;
		else if(d1[v]+cs[i]>d2[x])d2[x]=d1[v]+cs[i];
	}
}
void p(int x,int fa,int dis){
	ans[x]=max(dis,d1[x]);
	for(int i=hd[x];i;i=nt[i]){int v=vt[i];if(v==fa)continue;if(v==s[x])p(v,x,max(d2[x],dis)+cs[i]);else p(v,x,max(d1[x],dis)+cs[i]);}
}
int main(){
	while(cin>>n){
		cnt=0;
		memset(hd,0,sizeof(hd));
		memset(d1,0,sizeof(d1));
		memset(d2,0,sizeof(d2));
		for(int i=2;i<=n;i++)cin>>x>>y,add(i,x,y),add(x,i,y);
		it(1,0);
		p(1,0,0);
		for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
	}
	return 0;
}