[NOIp2018提高组]赛道修建
题目大意：
给你一棵\(n(n\le5\times10^4)\)个结点的树，从中找出\(m\)个没有公共边的路径，使得第\(m\)长的路径最长。问第\(m\)长的路径最长可以是多少。
思路：
二分答案+树形DP。\(f[x]\)表示以\(x\)为根的子树中最多能找出几个长度\(\ge k\)的路径。\(g[x]\)表示去掉已经满足的路径，从\(x\)子树内往上连的最长的路径有多长。
转移时将所有子结点的贡献\(g[y]+w\)排序。若贡献已经\(\ge k\)，那么就直接计入答案。否则从小到大枚举每一个贡献，找到能与其配对的最小的贡献，计入答案。如果找不到能与之配对的贡献，那么就用它来更新\(g[x]\)。可以证明这样能够在保证\(f[x]\)最大化的情况下，最大化\(g[x]\)。
时间复杂度\(\mathcal O(n\log n\log\)值域\()\)。
源代码：
#include<set>
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<algorithm>
inline int getint() {register char ch;while(!isdigit(ch=getchar()));register int x=ch^'0';while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');return x;
}
const int N=5e4+1;
struct Edge {int to,w;
};
std::vector<Edge> e[N];
inline void add_edge(const int &u,const int &v,const int &w) {e[u].push_back((Edge){v,w});e[v].push_back((Edge){u,w});
}
std::multiset<int> t;
int f[N],g[N],len;
void dfs(const int &x,const int &par) {f[x]=0;for(auto &j:e[x]) {const int &y=j.to;if(y==par) continue;dfs(y,x);f[x]+=f[y];}for(auto &j:e[x]) {const int &y=j.to;if(y==par) continue;t.insert(g[y]+j.w);}while(!t.empty()) {const int u=*t.rbegin();if(u>=len) {f[x]++;t.erase(t.find(u));} else {break;}}g[x]=0;while(!t.empty()) {const int u=*t.begin();t.erase(t.begin());auto p=t.lower_bound(len-u);if(p==t.end()) {g[x]=u;} else {t.erase(p);f[x]++;}}t.clear();
}
inline int calc(const int &k) {len=k;dfs(1,0);return f[1];
}
int main() {const int n=getint(),m=getint();int l=INT_MAX,r=0;for(register int i=1;i<n;i++) {const int u=getint(),v=getint(),w=getint();add_edge(u,v,w);l=std::min(l,w);r+=w;}while(l<=r) {const int mid=(l+r)>>1;if(calc(mid)>=m) {l=mid+1;} else {r=mid-1;}}printf("%d\n",l-1);return 0;
}
