P5021 [NOIP 2018 提高组] 赛道修建

题意简述

给定一棵含 $n$ 个点的无向带权树，求将其分裂为 $m$ 条链后，最短的一条链的最大长度是多少？

点可以重复使用，边不可以重复使用。

思路

二分答案贪心判定貌似可以？

看一下数据规模。

$a_i=1$ ，菊花图。链最多含两条边。

$b_i=a_i+1$ ，整棵树是一条链。

分支不超过 $3$ ？感觉在有意引导。是二叉树。

菊花图是最有用的，考虑菊花图时如何求解。设当前二分出的赛道长度为 $mid$ ：

显然此时一条链最多含两条边，考虑按边权排序：

1**.已经大于 $mid$ 的边**不必再拼接其他边，因为它已经能产生贡献了，再与其他边拼接，自身贡献不变的同时，阻止了其他边产生贡献的可能，必然不优。

2.剩下的边里，从小到大，对于每个边 $x$ ，二分（减小查询复杂度）查询出与它拼接能产生长度大于 $mid$ 的最短的一条边，即找到最小的 $y$ ，满足 $x+y\ge mid$ 。

为什么？如果用更长的边（ $>y$ ），那么可能会使得原本可以产生贡献的 $y$ 被抛弃，又因为自身不够长而无法再次与别的边产生贡献，相反，被使用的更长边显然更有可能与别的边拼接产生贡献，因此选择最小的 $y$ 即可。

菊花图的情况已经可以求解。不妨把每一个子树视作上述菊花图的情况，现在子树内已经得到最优解，如何向父节点扩展？

由于每个结点到父节点的边是唯一的，那么只能选择一条边传递给父节点，供后续产生贡献，那么，不难想到传递 剩余未匹配边 中最长的一条。因为最长，后续产生贡献的概率越大，缓解了父节点的匹配压力，保证了全局最优解。可以用 $dp[u]$ 表示当前结点最长未匹配边，到父节点出只需将父节点的边权加上 $dp[u]$ 即可。

当子树求解完成时，与子节点相连的边指向哪里已经不再重要，只需记录并排序边权即可，用 $multiset$ 。

代码实现

其实细节很多：

1.C++11 及以上： erase 返回删除指定元素后下一个有效迭代器。

2.在 $multiset$ 中查找到第一个大于等于 $y$ 的元素时一定要判断，有可能就是自己，如果未判断就删除会引起各种奇怪错误。

3. 我因为 $res=m$ 放在 $dfs$ 后，调了半天全输出 $0$。

#include <bits/stdc++.h>using namespace std;const int N = 5e4 + 100;
int n,m,L = INT_MAX,R,res,ans; 
bool vis[N];
struct Edges{int v,w;
};
vector <Edges> gra[N];void read(int &res){int x = 0,w = 1;char ch = 0;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = (x << 3) + (x << 1) + (ch - '0');ch = getchar();}res = x * w;
}bool cmp(Edges a,Edges b){return a.w < b.w;
}int dfs(int u,int limit){vis[u] = true;//记录与子树相连的边 int cnt = 0;multiset <int> match;//优先在子树内求解for(auto edge : gra[u]){int v = edge.v;//连接父亲的边跳过 if(vis[v]) continue;match.insert(edge.w + dfs(v,limit));} //在当前子树匹配//长度已经满足的 for(auto it = match.begin();it != match.end();)if(*it >= limit){it = match.erase(it);res--;  }else{it++;}
//	需要两两匹配的for(auto it = match.begin();it != match.end();){int y = limit - (*it);auto _it = match.lower_bound(y);if(_it == match.end() || _it == it){it++;continue; } res--;match.erase(_it);it = match.erase(it);} if(match.empty()) return 0;return *match.rbegin();
}void solve(){int l = L,r = R,mid;while(l <= r){mid = l + r >> 1;memset(vis,false,sizeof(vis));res = m;dfs(1,mid);if(res <= 0){l = mid + 1;ans = mid;}else r = mid - 1;	}printf("%d\n",ans);
} int main(){read(n);read(m);int u,v,w;for(int i = 1;i < n;i++){read(u);read(v);read(w);gra[u].push_back({v,w});gra[v].push_back({u,w});L = min(L,w);R += w;}//二分答案solve(); return 0;
}

挺好的一道树上二分+贪心。