记录编号	580899	评测结果	AAAAAAAAAA
题目名称	[HDOJ 2196]计算机	最终得分	100
用户昵称	在大街上倒立游泳	是否通过	通过
代码语言	C++	运行时间	1.029 s
提交时间	2023-07-27 15:44:04	内存使用	3.09 MiB

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    vector<int> ez,f,s,ying;
}tree[10004];
int ans[10004];
void dp(int last,int x,int pos){//来的点，当前点，last所处的下标 
    if(last!=0){
        if(tree[x].f[pos]) return;
        //for(int i=0;i<tree[x].ez.size();i++) if(tree[x].ez[i]==last&&tree[x].f[i]) return;
    }
    for(int i=0;i<tree[x].ez.size();i++){
        int y=tree[x].ez[i];
        if(y!=last) dp(x,y,tree[x].ying[i]);
    }
    for(int i=0;i<tree[x].ez.size();i++){
        int y=tree[x].ez[i];
        if(last!=0&&y!=last) tree[x].f[pos]=max(tree[x].f[pos],tree[y].f[tree[x].ying[i]]+tree[x].s[i]);
        else ans[x]=max(ans[x],tree[y].f[tree[x].ying[i]]+tree[x].s[i]);
        //if(last==0) cout<<tree[y].f[tree[x].ying[i]]+tree[x].s[i]<<"****";
    }
    //cout<<last<<' '<<x<<' '<<pos<<' '<<ans[x]<<endl;
}
int main(){
    freopen("computer_cable.in","r",stdin);
    freopen("computer_cable.out","w",stdout);
    while(cin>>n){
        int x,y;
        memset(tree,0,sizeof(tree));
        memset(ans,0,sizeof(ans));
        for(int i=2;i<=n;i++){
            cin>>x>>y;
            tree[x].ez.push_back(i);
            tree[x].f.push_back(0);
            tree[x].s.push_back(y);
            tree[i].ez.push_back(x);
            tree[i].f.push_back(0);
            tree[i].s.push_back(y);
            tree[x].ying.push_back(tree[i].ez.size()-1);
            tree[i].ying.push_back(tree[x].ez.size()-1);
        }
        for(int i=1;i<=n;i++) {
            dp(0,i,-1);
            cout<<ans[i]<<endl;
        }
    }
    return 0;
}