记录编号 |
586495 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[HDOJ 2196]计算机 |
最终得分 |
100 |
用户昵称 |
┭┮﹏┭┮ |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.000 s |
提交时间 |
2024-01-27 20:09:53 |
内存使用 |
0.00 MiB |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e4+10;
int n;
struct made{
int ver,nx,ed;
}e[N<<2];
int hd[N],tot,f[N][2];//最大次大
void add(int x,int y,int z){
tot++;
e[tot].nx = hd[x],e[tot].ver = y,e[tot].ed = z,hd[x] = tot;
}
void first(){
tot = 0;
memset(f,0,sizeof f);
memset(hd,0,sizeof hd);
}
void dfs1(int x,int fa){
for(int i = hd[x];i;i = e[i].nx){
int y = e[i].ver,z = e[i].ed;
if(y == fa)continue;
dfs1(y,x);
if(f[y][0] + z > f[x][0])f[x][1] = f[x][0],f[x][0] = f[y][0] + z;
else f[x][1] = max(f[x][1],f[y][0]+z);
//更新
}
}
void dfs2(int x,int fa){
for(int i = hd[x];i;i = e[i].nx){
int y = e[i].ver,z = e[i].ed;
if(y == fa)continue;
if(f[x][0] == f[y][0] + z){
if(f[x][1] + z > f[y][0])f[y][1] = f[y][0],f[y][0] = f[x][1] + z;
else f[y][1] = max(f[y][1],f[x][1] + z);
}
else{
if(f[x][0] + z > f[y][0])f[y][1] = f[y][0],f[y][0] = f[x][0] + z;
else f[y][1] = max(f[y][1],f[x][0] + z);
}
dfs2(y,x);
}
}
int main(){
freopen("computer_cable.in","r",stdin);
freopen("computer_cable.out","w",stdout);
while(~scanf("%d",&n)){
first();
for(int i = 2;i <= n;i++){
int x,z;
scanf("%d%d",&x,&z);
add(x,i,z),add(i,x,z);
}
dfs1(1,0);
dfs2(1,0);
for(int i = 1;i <= n;i++)printf("%d\n",f[i][0]);
}
return 0;
}