企业官网建设流程全解析

P10962 Computer

题目描述

某学校在一段时间前购买了第一台计算机（因此这台计算机的编号是 1）。在最近几年中，学校又购买了N−1N-1N−1台新计算机。每台新计算机都连接到之前已经安装的计算机之一。学校的管理人员对网络运行缓慢感到担忧，想知道每台计算机需要发送信号的最大距离SiS_iSi​（即到最远计算机的电缆长度）。你需要提供这些信息。

提示：示例输入对应于此图。从图中可以看到，计算机 4 是距离计算机 1 最远的，因此S1=3S_1 = 3S1​=3。计算机 4 和 5 是距离计算机 2 最远的，因此S2=2S_2 = 2S2​=2。计算机 5 是距离计算机 3 最远的，因此S3=3S_3 = 3S3​=3。我们还得到S4=4S_4 = 4S4​=4，S5=4S_5 = 4S5​=4。

输入格式

输入文件包含多个测试用例。每个用例的第一行是自然数NNN（N≤10000N \leq 10000N≤10000），接下来的N−1N-1N−1行描述了计算机的连接情况。第iii行包含两个自然数——第iii台计算机连接的计算机编号和用于连接的电缆长度。电缆的总长度不超过10910^9109。输入行中的数字由空格分隔。

输出格式

对于每个用例，输出NNN行。第iii行必须包含第iii台计算机的数值SiS_iSi​（1≤i≤N1 \leq i \leq N1≤i≤N）。

输入输出样例 #1

输入 #1

5 1 1 2 1 3 1 1 1

输出 #1

3 2 3 4 4

说明/提示

（由 ChatGPT 4o 翻译）

C++实现

#include<bits/stdc++.h>#defineintlonglong#defineINF1e18#defineN1000005usingnamespacestd;structstar{intnext,to,val;}e[N];intT,n,head[N],cnt,siz[N],f[N],f2[N],g[N],ans;voidadd(intu,intv,intw){e[++cnt].next=head[u];head[u]=cnt;e[cnt].to=v;e[cnt].val=w;}voiddfs1(intx,intfa){for(inti=head[x];i;i=e[i].next){inty=e[i].to,d=e[i].val;if(y==fa)continue;dfs1(y,x);if(f[y]+d>f[x]){f2[x]=f[x];f[x]=f[y]+d;}elseif(f[y]+d>f2[x]){f2[x]=f[y]+d;}}}voiddfs2(intx,intfa){for(inti=head[x];i;i=e[i].next){inty=e[i].to,d=e[i].val;if(y==fa)continue;if(f[y]+d==f[x])g[y]=max(f2[x],g[x])+d;elseg[y]=max(f[x],g[x])+d;dfs2(y,x);}}signedmain(){ios::sync_with_stdio(false);while(cin>>n){for(inti=1;i<=n;i++)f[i]=f2[i]=g[i]=head[i]=0;cnt=0;for(inti=2,v,w;i<=n;i++){cin>>v>>w;add(i,v,w),add(v,i,w);}dfs1(1,0),dfs2(1,0);for(inti=1;i<=n;i++)cout<<max(g[i],f[i])<<endl;}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容