求调必关
查看原帖
求调必关
929540
小午2014楼主2025/2/4 14:19

90分

#include <bits/stdc++.h>
#define int long long
#define MAXN 1000010
using namespace std;
int n,u,v,w,m,b[MAXN],bb[MAXN],time1[MAXN],f[MAXN],flag,g[MAXN];
int st[MAXN][20],cost[MAXN][20],dep[MAXN];
struct Tree
{
	int u,v,w;
};
vector<Tree> p[MAXN];
vector<int> military,nmili;
vector<int> node,nnode;
void buildst(int x,int fa)
{
	for(int i=1;i<=19;i++) st[x][i]=st[st[x][i-1]][i-1],cost[x][i]=cost[x][i-1]+cost[st[x][i-1]][i-1];
	for(int i=0;i<p[x].size();i++)
		if(p[x][i].v!=fa)
		{
			dep[p[x][i].v]=dep[x]+1;
			st[p[x][i].v][0]=x;
			cost[p[x][i].v][0]=p[x][i].w;
			buildst(p[x][i].v,x);
		}
}
void dfs(int x,int fa)
{
    bool yezi=0;
	if(f[x])
	{
		return;
	}
	for(int i=0;i<p[x].size()&&!flag;i++){
		if(p[x][i].v!=fa){
            yezi=1;
			dfs(p[x][i].v,x);
        }
    }
}
bool cmp(int a,int b)
{
	return cost[a][0]>cost[b][0];
}
bool cmp2(int i,int j)
{
	return time1[i]<time1[j];
}
void Clear()
{
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	memset(time1,0,sizeof(time1));
	memset(bb,0,sizeof(bb));
	military.clear();
	node.clear();
	nmili.clear();
	nnode.clear();
}
bool check(int x)
{
	Clear();
	for(int i=1;i<=m;i++)
	{
		int t=b[i],sum=x;
		for(int j=17;j>=0;j--)
			if(dep[st[t][j]]&&dep[st[t][j]]!=1&&sum>=cost[t][j])
				sum-=cost[t][j],t=st[t][j];
		bb[i]=t;
		if(st[t][0]!=1) f[t]=1;
		else
		{
			time1[i]=x-sum+cost[t][0];
			military.push_back(i);
		}
	}
	
	for(int i=0;i<p[1].size();i++)
	{
		flag=0;
		dfs(p[1][i].v,1);
		if(!flag)
			node.push_back(p[1][i].v),g[p[1][i].v]=1;
	}
	
	if(node.size()>military.size()) return false;
	
	sort(military.begin(),military.end(),cmp2);
	if(military.size())
		for(int i=military.size()-1;i>=0;i--)
		{
			int t=bb[military[i]];
			if(g[t]==1&&time1[military[i]]+cost[t][0]>x) g[t]=-1;
			else nmili.push_back(military[i]);
		}
		
	if(node.size())
		for(int i=0;i<node.size();i++)
			if(g[node[i]]!=-1)
			    nnode.push_back(node[i]);
			    
	sort(nnode.begin(),nnode.end(),cmp);
	sort(nmili.begin(),nmili.end(),cmp2);
	
	if(nnode.size()>nmili.size()) return false;
	
	if(nnode.size())
		for(int i=0;i<nnode.size();i++)
		{
			if(cost[nnode[i]][0]+time1[nmili[i]]>x)
				return false;
		}
	return true;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
    	cin>>u>>v>>w;
    	p[u].push_back({u,v,w});
    	p[v].push_back({v,u,w});
	}
	cin>>m;
	for(int i=1;i<=m;i++) cin>>b[i];
	dep[1]=1;
	buildst(1,0);
	int L=0,R=10000000000000000,ans=-1;
	while(L<=R)
	{
		int mid=L+R>>1;
		if(check(mid)) R=mid-1,ans=mid;
		else L=mid+1;
	}
	cout<<ans;
	return 0;
}
2025/2/4 14:19
加载中...