目录
显示
题目链接
https://www.luogu.com.cn/problem/P5021
题解
(做完了这个月的奶牛月赛发现自己竟然独立把这题做出来了 233)
首先想到二分答案。给出一个答案 \(ans\),如何判断这个答案是否可行呢?
注意到对于一个点 \(u\),经过 \(u\) 的赛道只有两种情况:
- \(v_1 \to u \to v_2\),其中 \(v_1,v_2\) 都是 \(u\) 子树内的某个节点(特殊情况下其中一个点可以和 \(u\) 重合)。
- \(v \to u \to f\),其中 \(v\) 是 \(u\) 子树内的某个节点,\(f\) 是 \(u\) 的祖先节点。
显然,对于每一个 \(u\) 第二种赛道最多只有一种。
于是我们对每个节点 \(u\),维护其等待配对的子链列表。
能构成赛道的子链有两种情况:
- 某条子链长度已经达标(单独构成一条赛道);
- 两个子链的长度加起来达标(拼起来构成一条赛道)。
我们找到所有这样的子链完成配对,从没配对的子链中选取最长的一条传给其父亲节点。
最后统计总赛道数,如果成功修建了至少 \(m\) 条赛道则说明答案可行。
维护等待配对的子链列表可以用 multiset
,时间复杂度为 \(O(n \log^2 n)\)。
#include <cstring> #include <iostream> #include <algorithm> #include <set> using namespace std; struct node { int v,w,next; }e[100005]; int head[50005],n,m,cnt; int res,f[50005]; void addedge(int u,int v,int w) { e[++cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt; } int dfs(int u,int fa,int x) { multiset<int> s; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(v!=fa) { int tmp=dfs(v,u,x)+e[i].w; if(tmp>=x)res++; else s.insert(tmp); } } int maxl=0; while(!s.empty()) { auto it=s.lower_bound(x-*s.begin()); if(it==s.begin()&&s.count(*it)==1)it++; if(it==s.end()) { maxl=max(maxl,*s.begin()); s.erase(s.begin()); } else { res++; s.erase(it); s.erase(s.begin()); } } return maxl; } int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<n;i++) { int u,v,w; cin>>u>>v>>w; addedge(u,v,w); addedge(v,u,w); } int l=1,r=1e9,ans=0; while(l<=r) { int mid=(l+r)>>1; memset(f,0,sizeof(f)); res=0,dfs(1,0,mid); if(res>=m)ans=mid,l=mid+1; else r=mid-1; } cout<<ans<<endl; return 0; }