10分求助
查看原帖
10分求助
758766
dkh2007楼主2024/7/31 16:41
#include<bits/stdc++.h>
#define int long long 
#define x first
#define y second
using namespace std;
const int N=6e4+10,M=N*2,K=23;
typedef pair<int,int>PII;
int h[N],e[M],ne[M],w[M],ids;
void add(int a,int b,int c)
{
	e[ids]=b,ne[ids]=h[a],w[ids]=c,h[a]=ids++;
}

int n,m;
int f[N][K],dis[N][K],pos[N];

void dfs(int u,int fa)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa) continue;
		f[j][0]=u,dis[j][0]=w[i];
		for(int k=1;k<K;k++) f[j][k]=f[f[j][k-1]][k-1],dis[j][k]=dis[j][k-1]+dis[f[j][k-1]][k-1];
		dfs(j,u);
	}
}
bool need[N],vis[N];
priority_queue<PII,vector<PII>,greater<PII>>heap;
bool dfs1(int x,int fa)
{
	bool lea=0;
	if(vis[x]) return 1;
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa) continue;
		lea=1;
		if(!dfs1(j,x)) return 0;
	}	
	
	if(!lea) return 0;
	return 1; 
}
int now[N],arm[N];
bool check(int tim)
{
	
	memset(vis,0,sizeof vis);
	memset(need,0,sizeof need);
	memset(now,0,sizeof now);
	memset(arm,0,sizeof arm);
	
	int t=log2(n);
	for(int i=1;i<=m;i++)
	{
		int cnt=0,x=pos[i];
		for(int j=t;j>=0;j--)	if(f[x][j]>1&&cnt+dis[x][j]>=tim) cnt+=dis[x][j],x=f[x][j];
		
		if(f[x][0]==1&&tim-cnt-dis[x][0]>=0) heap.push({tim-cnt-dis[x][0],x});//pay attention
		else vis[x]=1;
	}
	
	for(int i=h[1];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(!dfs1(j,-1)) need[j]=1;
	}
	
	int atot=0,btot=0;
	while(heap.size())
	{
		auto t=heap.top();heap.pop();
		
		if(need[t.y]&&dis[t.y][0]>t.x) need[t.y]=0;
		else arm[++atot]=t.x;		
	}
	
	for(int i=h[1];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(need[j]) now[++btot]=dis[j][0];
	}
	if(atot<btot) return 0;
	sort(now+1,now+1+btot),sort(arm+1,arm+1+atot);
	int i=1,j=1;
	while(i<=atot&&j<=btot)
	{
		
		if(now[j]<=arm[i]) i++,j++;
		else i++;
	}
	
	if(i>j) return 0;
	return 1;
}

int l,r,flag;
 main()
{
	memset(h,-1,sizeof h);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c),add(b,a,c);
		r+=c;
	}
	cin>>m;
	for(int i=1;i<=m;i++) cin>>pos[i];
	
	dfs(1,-1);
	int ans=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid-1,flag=1,ans=mid;
		else l=mid+1;
	}
	
	if(!flag) puts("-1");
	else cout<<ans<<endl;
	
	return 0;
}

2024/7/31 16:41
加载中...