[洛谷 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注