P10962 Computer题目描述某学校在一段时间前购买了第一台计算机因此这台计算机的编号是 1。在最近几年中学校又购买了N−1N-1N−1台新计算机。每台新计算机都连接到之前已经安装的计算机之一。学校的管理人员对网络运行缓慢感到担忧想知道每台计算机需要发送信号的最大距离SiS_iSi即到最远计算机的电缆长度。你需要提供这些信息。提示示例输入对应于此图。从图中可以看到计算机 4 是距离计算机 1 最远的因此S13S_1 3S13。计算机 4 和 5 是距离计算机 2 最远的因此S22S_2 2S22。计算机 5 是距离计算机 3 最远的因此S33S_3 3S33。我们还得到S44S_4 4S44S54S_5 4S54。输入格式输入文件包含多个测试用例。每个用例的第一行是自然数NNNN≤10000N \leq 10000N≤10000接下来的N−1N-1N−1行描述了计算机的连接情况。第iii行包含两个自然数——第iii台计算机连接的计算机编号和用于连接的电缆长度。电缆的总长度不超过10910^9109。输入行中的数字由空格分隔。输出格式对于每个用例输出NNN行。第iii行必须包含第iii台计算机的数值SiS_iSi1≤i≤N1 \leq i \leq N1≤i≤N。输入输出样例 #1输入 #15 1 1 2 1 3 1 1 1输出 #13 2 3 4 4说明/提示由 ChatGPT 4o 翻译C实现#includebits/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].nexthead[u];head[u]cnt;e[cnt].tov;e[cnt].valw;}voiddfs1(intx,intfa){for(intihead[x];i;ie[i].next){intye[i].to,de[i].val;if(yfa)continue;dfs1(y,x);if(f[y]df[x]){f2[x]f[x];f[x]f[y]d;}elseif(f[y]df2[x]){f2[x]f[y]d;}}}voiddfs2(intx,intfa){for(intihead[x];i;ie[i].next){intye[i].to,de[i].val;if(yfa)continue;if(f[y]df[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(cinn){for(inti1;in;i)f[i]f2[i]g[i]head[i]0;cnt0;for(inti2,v,w;in;i){cinvw;add(i,v,w),add(v,i,w);}dfs1(1,0),dfs2(1,0);for(inti1;in;i)coutmax(g[i],f[i])endl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3528）用C++实现信奥题 P10962 Computer
P10962 Computer题目描述某学校在一段时间前购买了第一台计算机因此这台计算机的编号是 1。在最近几年中学校又购买了N−1N-1N−1台新计算机。每台新计算机都连接到之前已经安装的计算机之一。学校的管理人员对网络运行缓慢感到担忧想知道每台计算机需要发送信号的最大距离SiS_iSi即到最远计算机的电缆长度。你需要提供这些信息。提示示例输入对应于此图。从图中可以看到计算机 4 是距离计算机 1 最远的因此S13S_1 3S13。计算机 4 和 5 是距离计算机 2 最远的因此S22S_2 2S22。计算机 5 是距离计算机 3 最远的因此S33S_3 3S33。我们还得到S44S_4 4S44S54S_5 4S54。输入格式输入文件包含多个测试用例。每个用例的第一行是自然数NNNN≤10000N \leq 10000N≤10000接下来的N−1N-1N−1行描述了计算机的连接情况。第iii行包含两个自然数——第iii台计算机连接的计算机编号和用于连接的电缆长度。电缆的总长度不超过10910^9109。输入行中的数字由空格分隔。输出格式对于每个用例输出NNN行。第iii行必须包含第iii台计算机的数值SiS_iSi1≤i≤N1 \leq i \leq N1≤i≤N。输入输出样例 #1输入 #15 1 1 2 1 3 1 1 1输出 #13 2 3 4 4说明/提示由 ChatGPT 4o 翻译C实现#includebits/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].nexthead[u];head[u]cnt;e[cnt].tov;e[cnt].valw;}voiddfs1(intx,intfa){for(intihead[x];i;ie[i].next){intye[i].to,de[i].val;if(yfa)continue;dfs1(y,x);if(f[y]df[x]){f2[x]f[x];f[x]f[y]d;}elseif(f[y]df2[x]){f2[x]f[y]d;}}}voiddfs2(intx,intfa){for(intihead[x];i;ie[i].next){intye[i].to,de[i].val;if(yfa)continue;if(f[y]df[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(cinn){for(inti1;in;i)f[i]f2[i]g[i]head[i]0;cnt0;for(inti2,v,w;in;i){cinvw;add(i,v,w),add(v,i,w);}dfs1(1,0),dfs2(1,0);for(inti1;in;i)coutmax(g[i],f[i])endl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容