赛道修建

[Time Gate]

https://www.luogu.org/problem/P5021

 【解题思路】

首先二分答案，贪心计算对于 mid的最大可能答案，判断它和 m的大小。我们称从一条赛道两端点 LCALCALCA 开始的，到一个端点结束的链为对应赛道的半链，令 fi 为以 ii为 LCA 的最优半链长度。要求对于 i 所有儿子的 f在保证两两匹配数（两个半链合成一条赛道）最多的同时，向 fi转移尽可能大的值。于是将所有 fff 排序贪心找到最大匹配数，然后，二分找到转移给 fif_ifi? 的值。

【code】

 1 #include <bits/stdc++.h>
 2 #define mid ((l+r)>>1)
 3 #define ll long long
 4 #define maxn 50010
 5 using namespace std;  6 struct Edge{  7     int to,next,val;  8     Edge(int a=0,int b=0,int c=0){  9         to=a,next=b,val=c; 10  } 11 }l[maxn<<1]; 12 int head[maxn],cnt,n,m; 13 vector<int> son[maxn]; 14 ll f[maxn]; 15 int subans[maxn]; 16 void Add(int a,int b,int c){ 17     l[++cnt]=Edge(b,head[a],c); 18     head[a]=cnt; 19 } 20 int check(int u,int pos,int tot,ll x){ 21     int res=0,l=0; 22     for (register int r=tot-1;r;--r){ 23         r-=r==pos; 24         while (l<r&&son[u][l]+son[u][r]<x) ++l; 25         l+=l==pos; 26         if (l>=r) break; 27         ++res;++l; 28  } 29     return res; 30 } 31 void Dfs(int u,int fa,ll x){ 32     f[u]=subans[u]=0; 33  son[u].clear(); 34     for (register int i=head[u];i;i=l[i].next){ 35         int v=l[i].to; 36         if (v==fa) continue; 37  Dfs(v,u,x); 38         f[v]+=l[i].val; 39         if (f[v]>=x) subans[u]++; 40         // 如果已经大于 x 则直接计入答案
41         else son[u].push_back(f[v]); 42  } 43     int tot=son[u].size(); 44  sort(son[u].begin(),son[u].end()); 45     int l=0,r=tot,sub=0,res; 46     for (register int r=tot-1;r;--r){ 47         while (l<r&&son[u][l]+son[u][r]<x) ++l; 48         if (l>=r) break; 49         ++sub;++l; 50  } 51     subans[u]+=sub; 52     // 贪心找出最大的匹配数（两个半链合成一条赛道）
53     if (sub*2==tot) return; 54     l=0,r=tot-1; 55     while(l<=r){ 56         int tem=check(u,mid,tot,x); 57         if (tem==sub) res=mid,l=mid+1; 58         else r=mid-1; 59  } 60     // 二分找到满足最大匹配的，可以转移给 f_u 的最大值
61     f[u]=son[u][res]; 62 } 63 bool check(ll x){ 64     int tem=0; 65     Dfs(1,0,x); 66     for (register int i=1;i<=n;++i) 67         tem+=subans[i]; 68     return tem>=m; 69 } 70 int main(){ 71     ll l=0,r=0,ans,c; 72     scanf("%d%d",&n,&m); 73     for (register int i=1,a,b;i<n;++i) 74         scanf("%d%d%lld",&a,&b,&c), 75         Add(a,b,c),Add(b,a,c),r+=c; 76     r/=(ll)m; 77     // 在这里二分答案
78     while(l<=r){ 79         if (check(mid)) ans=mid,l=mid+1; 80         else r=mid-1; 81  } 82     printf("%lld\n",ans); 83     return 0; 84 }