打卡信奥刷题（3094）用C++实现信奥题 P7162 [COCI 2020/2021 #2] Sjekira

张开发
• 2026/4/15 12:38:17 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

打卡信奥刷题（3094）用C++实现信奥题 P7162 [COCI 2020/2021 #2] Sjekira
P7162 [COCI 2020/2021 #2] Sjekira题目描述有一棵n nn个结点的树每个结点有一个权值删除一条边的费用为该边连接子树中结点权值最大值之和。问以任意顺序删除树中所有边的最小花费。输入格式第一行一个整数n nn表示结点数。第二行n nn个整数t 1 , t 2 , … , t n t_1, t_2, \ldots , t_nt1​,t2​,…,tn​其中第i ii个数表示结点i ii的权值。接下来n − 1 n-1n−1行每行两个整数x , y x, yx,y表示x xx和y yy之间有一条边。输出格式输出一个数代表最小花费。输入输出样例 #1输入 #13 1 2 3 1 2 2 3输出 #18输入输出样例 #2输入 #24 2 2 3 2 1 3 3 2 4 3输出 #215输入输出样例 #3输入 #35 5 2 3 1 4 2 1 3 1 2 4 2 5输出 #326说明/提示【样例解释 #1】先删( 2 , 3 ) (2,3)(2,3)再删( 1 , 2 ) (1,2)(1,2)花费为5 3 8 538538。【数据范围】对于100 % 100\%100%的数据1 ≤ n ≤ 100 , 000 1 \leq n \leq 100,0001≤n≤100,0001 ≤ t i ≤ 10 9 1 \leq t_i \leq 10^91≤ti​≤109。Subtask #110 1010ptsn ≤ 10 n \leq 10n≤10。Subtask #210 1010ptsi ii与i − 1 i-1i−1有边直接相连。Subtask #330 3030ptsn ≤ 1000 n \leq 1000n≤1000。Subtask #450 5050pts无附加限制。【说明】译自 Croatian Open Competition in Informatics 2020 ~ 2021 Round 2 D Sjekira。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;intn,sum,maxa,a[1000005]/*权值*/;signedmain(){cinn;//输入for(registerinti1;in;i){cina[i];suma[i];//总和maxamax(a[i],maxa);//最大值}sum-maxa;//利用公式for(registerinti1;in-1;i){intx,y;cinxy;summax(a[x],a[y]);//利用公式}coutsum;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

更多文章