526互联

P1084疫情控制 题解

发布时间 2023-10-14 16:22:15作者: Gdfzlcx

P1084疫情控制

前言：这题思路不难，实现稍微有点难。总体来说，不算特别难的那种紫题，建议评蓝。

题目描述

给定一些点，用这些点来切断根节点到所有叶子节点的路径，可以移动这些点,不同的点可以同时移动，求时间最少。

思考过程

  1. 不同的点可以同时移动：看到这里，我们可以转化一下题目：

    给定一些点，用这些点来切断根节点到所有叶子节点的路径，可以 移动这些点，求移动时间最长的点移动时间的最小值。

    然后我们就想到二分答案。

  2. 二分的check（贪心）：

    我们可以知道一个节点的子树所包含的叶子节点数一定大于等于这个节点的子节点的子树所包含的叶子节点数。所以我们希望检查点所在的节点深度越小越好。那么，我们可以先让一些在时间范围之内跳不到根节点的军队调到他能跳到最浅的节点建立检查点，其他军队调到根节点的子节点进行储备。然后，我们找到所有仍然可以被感染的节点。在找出所有没有建立检查点的军队，将他们匹配。判断是否成功就成功的二分啦。

  3. 倍增 :一个一个跳太慢，\(2^{i}\),\(2^{i-1}\)....2,1 的跳才快。

代码（不用注释了吧）

/*
	Problem:P1084
	Author:lougu#756336
	Oneline Judge:luogu
	Solution:树上倍增+二分+贪心
	warning:no
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+10,M=1e5+10,log_N=20;
int n,m;
int l,r,ans,flag,t_tot,d_tot,a_tot;
int a[N],dis[N][log_N],f[N][log_N];
int head[N],nxt[M],to[M],w[M],idx;
bool vis[N],need[N];
int ti[N],di[N];
pair<int,int> ar[N];
void add(int x,int y,int z){to[++idx]=y,w[idx]=z,nxt[idx]=head[x],head[x]=idx;}
void dfs_bz(int x,int fa,int dist)
{
	f[x][0]=fa,dis[x][0]=dist;
	for(int i=1;i<log_N;i++)
	{
		f[x][i]=f[f[x][i-1]][i-1];
		dis[x][i]=dis[x][i-1]+dis[f[x][i-1]][i-1];
	}
	for(int i=head[x];i;i=nxt[i])
	{
		if(to[i]==fa)continue;
		dfs_bz(to[i],x,w[i]);
	}
}
bool dfs(int x,int fa)
{
	bool fl=0;
	if(vis[x])return 0;
	for(int i=head[x];i;i=nxt[i])
	{
		if(to[i]==fa)continue;
		fl=1;
		if(dfs(to[i],x))return 1;
	}
	if(!fl)return 1;
	return 0;
}
bool check(int lim)
{
	memset(vis,0,sizeof vis);
	memset(ti,0,sizeof ti);
	memset(di,0,sizeof di);
	memset(ar,0,sizeof ar);
	memset(need,0,sizeof need);
	t_tot=d_tot=a_tot=0;
	for(int i=1;i<=m;i++)
	{
		int x=a[i],cnt=0;
		for(int j=log_N-1;j>=0;j--)
			if(f[x][j]>1&&cnt+dis[x][j]<=lim)
				cnt+=dis[x][j],x=f[x][j];
		if(f[x][0]==1&&cnt+dis[x][0]<=lim)
			ar[++a_tot]=make_pair(lim-cnt-dis[x][0],x);
		else vis[x]=1;
	}
	for(int i=head[1];i;i=nxt[i])need[to[i]]=dfs(to[i],1);
	sort(ar+1,ar+a_tot+1);
	for(int i=1;i<=a_tot;i++)
		if(need[ar[i].second]&&ar[i].first<dis[ar[i].second][0])
			need[ar[i].second]=0;
		else ti[++t_tot]=ar[i].first;
	for(int i=head[1];i;i=nxt[i])
		if(need[to[i]])di[++d_tot]=dis[to[i]][0];
	if(t_tot<d_tot)return 0; 
	sort(ti+1,ti+t_tot+1),sort(di+1,di+d_tot+1);
	int i=1,j=1;
	while(i<=d_tot&&j<=a_tot)
		if(ti[j]>=di[i])i++,j++;
		else j++;
	if(i>d_tot)return 1;
	return 0;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1,x,y,z;i<n;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z),add(y,x,z);
		r+=z;
	}
	dfs_bz(1,0,0);
	scanf("%lld",&m);
	for(int i=1;i<=m;i++)
		scanf("%lld",&a[i]);
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))r=mid-1,ans=mid,flag=1;
		else l=mid+1;
	}
	if(!flag)printf("-1");
	else printf("%lld",ans);
	return 0;
}