[洛谷 5021,loj 2952][NOIP2018]赛道修建

题目链接

https://www.luogu.com.cn/problem/P5021

https://loj.ac/problem/2952

题解

（做完了这个月的奶牛月赛发现自己竟然独立把这题做出来了 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;
}