40pts代码求调
查看原帖
40pts代码求调
557892
n___j__z____楼主2023/10/28 13:24
#include <bits/stdc++.h>
#define ll   long long
#define to first
#define w second
#define mk(a,b) make_pair(a,b)
#define pr pair<int,int> 
using namespace std;
const int N=5e4+3;
vector<pr>v[N];
int n,to[N][20],m,p[N],f2[N],k,vis[N],f[N],c[N],j;
ll w[20][N],d[N],l,r;
pr a[N];
bool cmp(pr a,pr b){
	return a.w>b.w;
}
void dfs1(int u,int fa){
	f2[u]=f2[fa];
	if(fa==1) f2[u]=u;
	for(int i=1;i<=15;i++)
		w[i][u]=w[i-1][u]+w[i-1][to[i-1][u]],
		to[i][u]=to[i-1][to[i-1][u]];
	for(pr i:v[u])if(i.to!=fa){
		w[0][i.to]=i.w,to[0][i.to]=i.to,d[i.to]=d[u]+i.w;
		dfs1(i.to,u);
	}
}
int To(int u,int lim){
	for(int i=15;i>=0;i--)
		if(lim>=w[i][u]) lim-=w[i][u],u=to[i][u];
	return u;
}
void dfs(int u,int fa){
	if(f[u]) return;
	int flag=0;
	for(pr i:v[u])if(i.to!=fa){
		dfs(i.to,u);flag=1;
		if(!f[i.to])return;
	}
	f[u]=flag;
}
bool no(int u,int lim){
	if(!vis[c[u]]){
		vis[c[u]]=1;
		return false;
	}
	while(j<=k&&vis[a[j].to]) j++;
	if(j>k||a[j].w<lim) return true;
	vis[a[j].to]=1,j++;
	return false;
}
bool check(ll lim){
	j=1,k=0;memset(vis,0,sizeof(vis));vis[0]=1;
	memset(f,0,sizeof(f));
	memset(c,0,sizeof(c));
	for(int i=1;i<=m;i++){
		if(d[p[i]]<=lim){
			k++;
			a[k]=mk(k,lim-d[p[i]]);
			if(!c[f2[p[i]]]||a[c[f2[p[i]]]].w>a[k].w) c[f2[p[i]]]=k;
		}
		else{
			f[To(p[i],lim)]=1;
//			  <<To(p[i],lim)<<endl;
		}
	}
	dfs(1,0);
	sort(a+1,a+1+k,cmp);
//	for(int i=1;i<=k;i++)   <<a[i].to<<" "<<a[i].w<<endl;
//	  <<c[2]<<endl<<endl;
	for(pr t:v[1]) if(!f[t.to])
		if(no(t.to,t.w)) return false;
	return true;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);  cout.tie(0);
	cin>>n;
	for(int i=1,x,y,ww;i<n;i++){
		cin>>x>>y>>ww;
		v[x].push_back(mk(y,ww));
		v[y].push_back(mk(x,ww));
		r+=ww;	
	}
	sort(v[1].begin(),v[1].end(),cmp);
	dfs1(1,0);
	cin>>m;
	for(int i=1;i<=m;i++) cin>>p[i];
	if(m<v[1].size()){
		cout  <<"-1";
		return 0;
	}
	while(l<=r){
		ll mid=(l+r)>>1;
		if(check(mid)) r=mid-1;
		else l=mid+1;
	}
	cout  <<r+1;
/*	  <<check(3);*/
	return 0;
}
2023/10/28 13:24
加载中...