一脸懵逼求调
查看原帖
一脸懵逼求调
1129446
nksunhaolan楼主2024/10/28 20:43
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll N=5e5+4;
ll n,m,n1,a,b,v;
ll head[N],cnt;
struct nnd {
	ll to,w,next;
}eg[N<<1];
struct mmb {
	ll from,to,w;
}A[N];
struct node{
	ll w,x;
};
struct hh {
	ll l,r,x;
};
ll dis[N],son[N],k,fa[N],B[N];bool last[N],vis[N];//DFS
ll loog[N],st[N][20],dp[N][20];//st表 
ll in[N],out[N],idx;//DFS序 
vector<node>C,D;
vector<hh>BF;

bool pai(mmb x,mmb y){
	return x.w < y.w ;
}
bool cmp(node x,node y){
	return x.w < y.w ;
}
bool hhh(hh x,hh y){
	return x.l < y.l ;
}
void init(){
	for(ll i=1;i<=n;i++)head[i]=-1;
	loog[0]=-1;
	for(ll i=1;i<=n;i++)loog[i]=loog[i>>1]+1;
}
void add(const ll& from,const ll& to,const ll& w){
	eg[cnt].to=to;
	eg[cnt].w=w;
	eg[cnt].next=head[from];
	head[from]=cnt++;
}
void dfs(const ll& x,const ll& f,ll fx){
	in[x]=++idx;
	if(f==1){
		fa[x]=fx=x;
	} else {
		fa[x]=fx;
	}
	st[x][0]=f;
	for(ll K=1;K<=loog[n];K++){
		st[x][K]=st[st[x][K-1]][K-1];
		if(st[x][k]==0){
			k=max(k,K);
			break;
		}
		dp[x][K]=dp[st[x][K-1]][K-1]+dp[x][K-1];
	}
	for(ll i=head[x];i!=-1;i=eg[i].next){
		ll to=eg[i].to;
		if(to!=f){
			dp[to][0]=eg[i].w;
			dfs(to,x,fx);
			son[x]+=son[to];
		}
	}
//	cout<<x<<":"<<fa[x]<<'\n';
	if(son[x]==0)son[x]++;
	out[x]=idx;
}
bool check(const ll& x){
	memset(dis,0,sizeof(dis));  
	memset(vis,0,sizeof(vis));  
	memset(last,0,sizeof(last));
	BF.clear();
	C.clear();D.clear();
	for(ll i=1;i<=m;i++){
		ll sum=x,y=B[i];
		for(ll j=k;j>=0;j--){
			if(st[y][j]==1 || st[y][j]==0 || dp[y][j]>x)continue;
			y=st[y][j];
			sum-=dp[y][j];
		}
//		cout<<y<<" ";
		if(st[y][0]==1){
			if(sum>dp[y][0]){
				vis[y]=1;
				C.push_back({sum-dp[y][0],y});	
			} else dis[y]+=son[y];
		} else BF.push_back({in[y],out[y],y});
	}
//	cout<<'\n';
	sort(BF.begin(),BF.end(),hhh);
	sort(C.begin(),C.end(),cmp);
	ll l=0;
	for(ll i=0;i<BF.size();i++){
		if(i==0 || !(BF[i].r<=BF[l].r)){
			l=i;
			dis[fa[BF[i].x]]+=son[BF[i].x];
		}
	}
	for(ll i=head[1];i!=-1;i=eg[i].next){
		ll to=eg[i].to;
		if(dis[to]<son[to]){
//			cout<<to<<" ";
			if(!vis[to])D.push_back({dp[to][0],to});
		} else {
			last[to]=1;
		}
	}
//	cout<<'\n';
	sort(D.begin(),D.end(),cmp);
//	for(int i=0;i<C.size();i++){
//		cout<<C[i].x<<" "<<C[i].w<<"\n";
//	}
//	for(int i=0;i<D.size();i++){
//		cout<<D[i].x<<" "<<D[i].w<<"\n";
//	}
//	for(int i=head[1];i!=-1;i=eg[i].next){
//		int to=eg[i].to;
//		cout<<to<<":"<<last[to]<<" ";
//	}
//	cout<<'\n';
	l=0;
	for(ll i=0;i<C.size();i++){
		ll z1=C[i].x,z2=D[l].x;
		if(z1==z2 || C[i].w>=dp[z2][0]){
//			cout<<z1<<" "<<z2<<'\n';
			if(!last[z1]){
				last[z1]=1;;
				continue;
			}
			l++;
			if(l==D.size())break;
		}
	}
//	for(int i=head[1];i!=-1;i=eg[i].next){
//		int to=eg[i].to;
//		cout<<to<<" "<<son[to]<<"|"<<dis[to]<<'\n';
//	}
	if(l>=D.size()){
		return 1;
	} else {
		return 0;
	}
}

int main(){
//	freopen("001.in","r",stdin); 
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	cin>>n;init();ll idx=0,l=0,r=0;
	for(ll i=1;i<n;i++){
		cin>>a>>b>>v;
		r+=v;
		if(a==1 || b==1){
			idx++;
			A[++n1].from=a;
			A[n1].to=b;
			A[n1].w=v;
		} else {
			add(a,b,v);
			add(b,a,v);
		}
	}
	sort(A+1,A+n1+1,pai);
	for(ll i=1;i<=n1;i++){
		add(A[i].from,A[i].to,A[i].w);
		add(A[i].to,A[i].from,A[i].w);
	}
	dfs(1,0,0);
//	for(int i=1;i<=n;i++){
//		cout<<in[i]<<" "<<out[i]<<'\n';
//	} 
//	for(int i=1;i<=n;i++)cout<<son[i]<<" ";
//	cout<<'\n';
	cin>>m;
	for(ll i=1;i<=m;i++){
		cin>>B[i];
	}
//	cout<<check(9);
	if(m<idx){
		cout<<"-1";
		return 0;
	}
	while(l<r){
		ll mid=l+r>>1;
		if(check(mid)){
			r=mid;
		} else {
			l=mid+1;
		}
	}
	cout<<l;
//	
//	return 0;
}
2024/10/28 20:43
加载中...