全flash网站,郑州发布官网,百度网页版无痕模式,微信公众号做特效的网站传送门
题意#xff1a;给一棵带边权的树#xff0c;求MMM条没有公共边的路径的最小长度的最大值。 N≤50000N \leq50000N≤50000
抛开NOIP不谈#xff0c;其实这题本身出的很好
显然二分
问题转化成了“最多可以找多少条长度不小于kkk的路径”
递归处理
对于每个结点…传送门
题意给一棵带边权的树求MMM条没有公共边的路径的最小长度的最大值。
N≤50000N \leq50000N≤50000
抛开NOIP不谈其实这题本身出的很好
显然二分
问题转化成了“最多可以找多少条长度不小于kkk的路径”
递归处理
对于每个结点iii先统计它的子树剩下的链加上当前边权。
现在我们得到了若干个数表示以iii为顶的还没用过的链的长度
我们希望用这些数凑出kkk
大于等于kkk的可以直接统计答案
有如下贪心策略从小到大二分最小的可以匹配的最后把不能匹配的最长的作为剩下的链传回去
为什么
首先很显然尽量匹配小的
如果我们留了一条很长的链不匹配而要传上去也最多产生111的贡献。而现在直接匹配也会有111的贡献不配白不配。
为什么从小到大
如果我们从大到小或者用一些神奇的顺序那就是出现大配小的情况。从小到大我们就算不匹配尽量小也能重现之前的状态尽量小就肯定更优了。
用multiset维护即可。
细节有点多。注意大于等于kkk的必须在开始弹掉否则可能浪费一个小的。
菊花图可能卡常可以跑个直径作为二分上限。
#include iostream
#include cstdio
#include cstring
#include cctype
#include set
#define MAXN 50005
#define MAXM 100005
using namespace std;
struct edge{int u,v,w;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt;
void addnode(int u,int v,int w)
{e[cnt](edge){u,v,w};nxt[cnt]head[u];head[u]cnt;
}
int dp[MAXN];
int count(int u,int f,int k)
{multisetint s;int ans0;for (int ihead[u];i;inxt[i])if (e[i].v!f){anscount(e[i].v,u,k);if (dp[e[i].v]e[i].wk) ans;else s.insert(dp[e[i].v]e[i].w);}while (!s.empty()){int mn*s.begin();multisetint::iterator ps.lower_bound(k-mn);if (ps.begin()) p;if (ps.end()){dp[u]max(dp[u],mn);s.erase(s.begin());continue;}ans;s.erase(p);s.erase(s.begin());}return ans;
}
int dis[MAXN];
void dfs(int u,int f)
{for (int ihead[u];i;inxt[i])if (e[i].v!f){dis[e[i].v]dis[u]e[i].w;dfs(e[i].v,u);}
}
int main()
{int n,m;scanf(%d%d,n,m);for (int i1;in;i){int u,v,w;scanf(%d%d%d,u,v,w);addnode(u,v,w);addnode(v,u,w);}dfs(1,0);int mx0;for (int i1;in;i) if (dis[i]dis[mx]) mxi;dis[mx]0;dfs(mx,0);int l0,r0,mid;for (int i1;in;i) rmax(r,dis[i]);while (lr){mid(lr1)1;memset(dp,0,sizeof(dp));if (count(1,0,mid)m) lmid;else rmid-1;}printf(%d\n,l);return 0;
}
