P10418 [蓝桥杯 2023 国 A] 相连的边

题目描述

给定一棵包含nnn个结点的树，找出333条边使得这三条边的端点仅经过这三条边即可互相到达且三条边的长度和尽可能大。

输入格式

输入第一行包含一个整数nnn表示树的结点数。

接下来n−1n−1n−1行，每行包含两个整数，用一个空格分隔。其中第iii行的两个数xi,yix_i,y_ixi​,yi​，表示编号为i+1i+1i+1和xix_ixi​的结点之间有一条长度为yiy_iyi​的边。

输出格式

输出一行，包含一个整数表示满足要求的三条边的长度之和的最大值。

输入输出样例 #1

输入 #1

5 1 1 2 1 3 7 1 10

输出 #1

12

说明/提示

【样例解释 1】

结点222和结点111的边长为111，结点333和结点222的边长为111，结点444和结点333的边长为777，结点555和结点111的边长为101010。

【评测用例规模与约定】

对于20%20\%20%的评测用例，4≤n≤3004\le n\le 3004≤n≤300；
对于40%40\%40%的评测用例，4≤n≤50004\le n\le 50004≤n≤5000；
对于所有评测用例，4≤n≤2×1054\le n\le 2\times 10^54≤n≤2×105，1≤xi<i1\le x_i<i1≤xi​<i，1≤yi≤1091\le y_i\le 10^91≤yi​≤109。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=(int)2e5+10;vector<pair<int,int>>g[N];intmain(){intn;cin>>n;for(inti=2;i<=n;i++){intx,y;cin>>x>>y;g[i].push_back({y,x});g[x].push_back({y,i});}longlongans=0;for(inti=1;i<=n;i++){sort(g[i].begin(),g[i].end(),greater<pair<int,int>>());if(g[i].size()>=3){ans=max(ans,0ll+g[i][0].first+g[i][1].first+g[i][2].first);}}for(inti=1;i<=n;i++){if(g[i].size()==1)continue;for(auto[y,x]:g[i]){if(g[x].size()==1)continue;longlongsum=y;sum+=(g[x][0].second!=i?g[x][0]:g[x][1]).first;sum+=(g[i][0].second!=x?g[i][0]:g[i][1]).first;ans=max(ans,sum);}}cout<<ans<<'\n';return0;}

后续

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