题解 P5021 【赛道修建】

首发于 [个人博客](https://zepto.page/post/noip-2018-track)。 ### 思路 我就顺着我考场上的思路，把所有部分分都讲一讲吧。 首先对于 $m=1$ 的数据，我们显然只要找到直径长度就行； 对于一条链的情况，二分答案，对于每次二分出来的 $mid$，从根开始贪心选取一段边，累计长度大于等于 $mid$ 的时候就计入答案，重新开始寻找下一段，得出对于 $mid$ 最大的答案，判断它是否大于 $m$； 对于菊花图，由于路径最多经过两条边，我们实质上是要在 $n-1$ 条边中选一共 $m$ 次，每次选出一条独立的边，或者一对边，使得最终每条边的长度 / 每对边的长度和尽量大。对于每次二分出来的 $mid$，长度大于 $mid$ 的边独立地选出，而小于 $mid$ 的边尝试一长一短两两配对，用双指针在排过序的长度数据中扫描一遍，得出对于 $mid$ 最大的答案，判断它是否大于 $m$； 对于 “分支不超过 3” 的图，也就是除根节点之外，每个点只有两个儿子，同样我们二分答案。首先定义几个概念，我们称从一条赛道两端点 $LCA$ 开始的，到一个端点结束的链为对应赛道的半链，令 $f_i$ 为以 $i$ 为 $LCA$ 的最优半链长度。暂时不考虑根节点，如果 $i$ 只有一个儿子 $v$，若 $f_v + l_i \geq mid$，直接将 $f_v + l_i$ 计入答案，否则，$f_i = f_v + l_i$；如果 $i$ 有两个儿子，如果它们可以直接单独计入答案则直接计入，否则考虑是否可以将这两个儿子牵引的两条半链合并，合并后长度大于 $mid$ 则直接计入答案，否则选取最长的一段转移到 $f_i$，对于可能有三个儿子的根节点，遵循的原则同样是尽量独立选取两个儿子，否则尝试合并两条半链计入答案； 如果我们结合菊花图和 “分支不超过 3” 的图这两种情况，我们就可以搞定 100% 的数据。继承上面半链和 $f_i$ 的定义，我们要做的是在使最多的儿子对答案做出贡献的同时，尽量大地将 $f_{son}$ 的值转移给 $f_i$。因为 $f$ 的一个值最多对答案产生 1 的贡献，所以使儿子做出更少贡献，转移更大的 $f_i$ 不可能使答案变优，我们的贪心第一关键字就可以设为使儿子做出最大的贡献。在菊花图的算法中，我们只满足了第一个条件，但不需要考虑 $f_i$ 进一步的转移，而我认为这一点正是 A 掉本题的重点。也就是说，我们要在儿子的 $f$ 值中，选出一个最优的转移至 $f_i$，使得剩下的 $f$ 值的合法匹配最多。同样可以二分转移至 $f_i$ 的儿子，剩下的和菊花图的做法相同。 总结一下正解：首先二分答案，贪心计算对于 $mid$ 的最大可能答案，判断它和 $m$ 的大小。我们称从一条赛道两端点 $LCA$ 开始的，到一个端点结束的链为对应赛道的半链，令 $f_i$ 为以 $i$ 为 $LCA$ 的最优半链长度。要求对于 $i$ 所有儿子的 $f$，在保证两两匹配数（两个半链合成一条赛道）最多的同时，向 $f_i$ 转移尽可能大的值。于是将所有 $f$ 排序贪心找到最大匹配数，然后，二分找到转移给 $f_i$ 的值。 复杂度不太会证，应该接近 $\Theta(n\log n \log \dfrac{\sum{l_i}}{m})$ 吧。 ### 代码 ```cpp #include <bits/stdc++.h> #define mid ((l+r)>>1) #define ll long long #define maxn 50010 using namespace std; struct Edge{ int to,next,val; Edge(int a=0,int b=0,int c=0){ to=a,next=b,val=c; } }l[maxn<<1]; int head[maxn],cnt,n,m; vector<int> son[maxn]; ll f[maxn]; int subans[maxn]; void Add(int a,int b,int c){ l[++cnt]=Edge(b,head[a],c); head[a]=cnt; } int check(int u,int pos,int tot,ll x){ int res=0,l=0; for (register int r=tot-1;r;--r){ r-=r==pos; while (l<r&&son[u][l]+son[u][r]<x) ++l; l+=l==pos; if (l>=r) break; ++res;++l; } return res; } void Dfs(int u,int fa,ll x){ f[u]=subans[u]=0; son[u].clear(); for (register int i=head[u];i;i=l[i].next){ int v=l[i].to; if (v==fa) continue; Dfs(v,u,x); f[v]+=l[i].val; if (f[v]>=x) subans[u]++; // 如果已经大于 x 则直接计入答案 else son[u].push_back(f[v]); } int tot=son[u].size(); sort(son[u].begin(),son[u].end()); int l=0,r=tot,sub=0,res; for (register int r=tot-1;r;--r){ while (l<r&&son[u][l]+son[u][r]<x) ++l; if (l>=r) break; ++sub;++l; } subans[u]+=sub; // 贪心找出最大的匹配数（两个半链合成一条赛道） if (sub*2==tot) return; l=0,r=tot-1; while(l<=r){ int tem=check(u,mid,tot,x); if (tem==sub) res=mid,l=mid+1; else r=mid-1; } // 二分找到满足最大匹配的，可以转移给 f_u 的最大值 f[u]=son[u][res]; } bool check(ll x){ int tem=0; Dfs(1,0,x); for (register int i=1;i<=n;++i) tem+=subans[i]; return tem>=m; } int main(){ ll l=0,r=0,ans,c; scanf("%d%d",&n,&m); for (register int i=1,a,b;i<n;++i) scanf("%d%d%lld",&a,&b,&c), Add(a,b,c),Add(b,a,c),r+=c; r/=(ll)m; // 在这里二分答案 while(l<=r){ if (check(mid)) ans=mid,l=mid+1; else r=mid-1; } printf("%lld\n",ans); return 0; } ```