颓了好几天，终于把这到题处理了一下。
话说，其实我考场上想出正解了，但是手残，算复杂度的时候多按了一个零，导致算出来是1亿多的复杂度，都不敢打。。。就把部分分都捡了一下。。。
C 城将要举办一系列的赛车比赛。在比赛前，需要在城内修建 m 条赛道。
C 城一共有 n 个路口，这些路口编号为 1,2,…,n1，有 n−1 条适合于修建赛道的双向通行的道路，每条道路连接着两个路口。其中，第 ii 条道路连接的两个路口编号为 ai? 和 bi?，该道路的长度为 li?。借助这 n-1n−1 条道路，从任何一个路口出发都能到达其他所有的路口。
一条赛道是一组互不相同的道路 e1,e2,…,ek满足可以从某个路口出发，依次经过 道路 e1,e2,…,ek?（每条道路经过一次，不允许调头）到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全，要求每条道路至多被一条赛道经过。
目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案，使得修建的 m 条赛道中长度最小的赛道长度最大（即 m 条赛道中最短赛道的长度尽可能大）
从部分分开始讲吧。
这个部分分还是挺好拿的，把边从大到小排序之后，直接二分答案。两个指针，i，正着来，j，倒着来，i就顺着取下去，对于每个i给它匹配一个最大的相加刚好大于二分值的j（一开始就大于二分值的要特殊处理），注意到这个决策是有单调性的，即：当i1小于i2时，那么相匹配的j1一定大于等于j2，这样的话，我们每次只要扫一遍就能得到答案（考完后有人和我说求菊花图要log2二分答案套二分，嗯，就是我们的zyk同志，其实我一直都觉得这个人的脑回路特别清奇。。。）。
这个的话其实就是正解的简化版了，考虑二分答案加树形DP。
dp[u]：表示以u为根的子树中有多少长度大于mid的链。
f[u]：表示以u为根的子树中，除去那些被统计到dp数组中的链，现在能传到父亲的链的长度最长的链的长度（貌似有点拗口呢。。。）。
转移应该很简单了吧。
首先，dp[u]=∑v∈u‘s sons 如果u的两个儿子的最长链加起来大于mid，那么再给dp[u]+1，f[u]=0，否则的话，f[u]=max(f[v1]，f[v2])。
正解其实就是把两者结合一下啦。
但是特别注意的就是：我们要在满足匹配数最大的情况下，找一条最长的链传给父亲。
那么这个要求我们应该怎么来实现呢？——二分嘛！
我们可以二分我们需要传上去的那条链，然后在匹配的时候跳过这条链就行了。（其实这是成一类dalao教我的）
（不得不说一句——C++压行是真的爽，啊哈哈哈！！！）
#include <bits/stdc++.h> using namespace std; const int maxn=50005; int dp[maxn],f[maxn],head[maxn],nxt[2*maxn],vet[2*maxn],dist[2*maxn]; int tot,mid; void add(int x,int y,int z){ tot++; nxt[tot]=head[x]; vet[tot]=y; head[x]=tot; dist[tot]=z; } bool cmp(int a,int b) { return a>b; } void dfs(int u,int father){ vector<int> a; for (int i=head[u];i;i=nxt[i]){ int v=vet[i]; if (v==father) continue; dfs(v,u); f[v]+=dist[i]; if (f[v]<mid) a.push_back(f[v]); else dp[u]++; dp[u]+=dp[v]; } int l=0,r=a.size()-1; sort(a.begin(),a.end(),cmp); a.push_back(0); int ans=a.size()-1,Max=0,i=0,j=a.size()-2; while (i<j) if (a[i]+a[j]>=mid) i++,j--,Max++; else j--; while (l<=r){ int now=(l+r)>>1,res=0,i=0,j=a.size()-2; while (i<j){ if (i==now) {i++; continue;} if (j==now) {j--; continue;} if (a[i]+a[j]>=mid) i++,j--,res++; else j--; } if (res>=Max) Max=res,ans=now,r=now-1; else l=now+1; } dp[u]+=Max; f[u]=a[ans]; } int main(){ int n,m; scanf("%d%d",&n,&m); for (int i=1;i<n;++i){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } int l=1,r=500000000,ans=0; while (l<=r){ memset(dp,0,sizeof(dp)); memset(f,0,sizeof(f)); mid=(l+r)>>1; dfs(1,0); if (dp[1]>=m) ans=mid,l=mid+1; else r=mid-1; } printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/WR-Eternity/p/9964177.html