30pts求调
查看原帖
30pts求调
464732
luqyou楼主2024/7/12 19:09
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10;
struct edge{
	int v,w;
};
struct army{
	int d,u;
	bool operator <(army _){
		return d<_.d;
	}
}r[maxn];
int n,m,dep[maxn],f[maxn][20],dis[maxn][20],a[maxn],b[maxn],lst[maxn],vis[maxn],fl[maxn];
int id[maxn],ld[maxn],cnta,cnt1,cnt2;
vector<edge> g[maxn];
void pre(int u,int fa){
	f[u][0]=fa,dep[u]=dep[fa]+1;
	for(int i=1;i<=19;i++) f[u][i]=f[f[u][i-1]][i-1],dis[u][i]=dis[u][i-1]+dis[dis[u][i-1]][i-1];
	for(edge e:g[u]) if(e.v!=fa) dis[e.v][0]=e.w,pre(e.v,u);
}
bool dfs(int u,int fa){
	if(vis[u]) return 0;
	int leaf=1,flg=0;
	for(edge e:g[u]) if(e.v!=fa) leaf=0,flg|=dfs(e.v,u);
	if(leaf) return 1;
	return flg;
}
bool chk(int x){
	cnt1=cnt2=cnta=0;
	for(int i=1;i<=m;i++) a[i]=b[i],lst[i]=0;
	for(int i=1;i<=n;i++) vis[i]=fl[i]=0;
	for(int i=1;i<=m;i++){
		int cnt=0,now=a[i];
		for(int j=19;j>=0;j--){
			if(f[now][j]>1&&cnt+dis[now][j]<=x){
				cnt+=dis[now][j];
				now=f[now][j];
			}
		}
//		if(x==3) cout<<a[i]<<"->"<<now<<" "<<cnt<<" "<<dis[now][0]<<endl;
		if(f[now][0]==1&&cnt+dis[now][0]<=x) r[++cnta]={x-cnt-dis[now][0],now};
		else vis[now]=1;
	}
	for(edge e:g[1]) fl[e.v]=dfs(e.v,1);
//	if(x==3) for(edge e:g[1]) cout<<e.v<<" "<<fl[e.v]<<endl;
	sort(r+1,r+cnta+1);
	for(int i=1;i<=cnta;i++){
		if(fl[r[i].u]&&r[i].d<dis[r[i].u][0]) fl[r[i].u]=0;
		else{
			ld[++cnt1]=r[i].d;
//			if(x==3) cout<<r.d<<endl;
		}
//		if(x==3) cout<<r.u<<" "<<fl[r.u]<<" "<<r.d<<" "<<dis[r.u][0]<<endl;
	}
	for(edge e:g[1]) if(fl[e.v]) id[++cnt2]=e.w;
//	if(x==3) cout<<"sizes:"<<cnt1<<" "<<cnt2<<endl;
	if(cnt2>cnt1) return 0;
//	cout<<"<s"<<endl;
	int z1=1,z2=1;
	sort(id+1,id+cnt2+1),sort(ld+1,ld+cnt1+1);
//	if(x!=3) goto debug; 
//	cout<<"need to do:";
//	for(int i=1;i<=cnt2;i++) cout<<id[i]<<" ";
//	cout<<endl;
//	cout<<"army you have:";
//	for(int i=1;i<=cnt1;i++) cout<<ld[i]<<" ";
//	cout<<endl; 
//	debug:;
	while(z1<=cnt1&&z2<=cnt2){
		if(ld[z1]>=id[z2]) z1++,z2++;
		else z1++;
	}
//	if(x==3) cout<<z1<<" "<<z2<<endl;
	return (z2>cnt2);
}
void solve(){
	cin>>n;
	for(int i=1,u,v,w;i<n;i++) cin>>u>>v>>w,g[u].push_back({v,w}),g[v].push_back({u,w});
	cin>>m,pre(1,0);
//	for(int i=1;i<=n;i++) cout<<dis[i][0]<<" ";
//	cout<<endl;
	for(int i=1;i<=m;i++) cin>>b[i];
	int l=1,r=1e14,mid;
	while(l<=r) mid=l+r>>1,(chk(mid)?(r=mid-1):(l=mid+1));
//	for(int i=1;i<=12;i++) cout<<i<<":"<<chk(i)<<endl;
	chk(3); 
	cout<<(l>=1e14?-1:l)<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--) solve();
	return 0;
}
/*
10
2 1 3
2 3 4
1 4 7
5 1 9
6 1 2
4 7 9
7 8 8
9 8 8
1 10 2
5
2 8 5 4 2
*/
2024/7/12 19:09
加载中...