WA ON #1,2,3,4,7

又臭又长而且常数巨大

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,cnt,hd[50005],fa[50005][20],dep[50005],l[50005];
bool vis[50005];
struct node{
	int to,next,dis;
}e[100005];
int read(){
	int f=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		f=f*10+ch-'0';
		ch=getchar();
	}
	return f*w;
}
void addedge(int x,int y,int z){
	e[++cnt].dis=z;
	e[cnt].next=hd[x];
	e[cnt].to=y;
	hd[x]=cnt;
}
struct Node{
	int pos,used,rest,now;
}w[50005];
bool cmp(Node a,Node b){
	return dep[a.pos]>dep[b.pos];
}
bool cmp1(Node a,Node b){
	if(a.used!=b.used) return a.used<b.used;
	else return a.rest-dep[a.now]<b.rest-dep[b.now];
}
void dfs(int x,int ff){
	for(int i=1;i<=19;i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=hd[x];i;i=e[i].next){
		int to=e[i].to;
		if(to!=ff){
			dep[to]=dep[x]+e[i].dis;
			l[to]=e[i].dis;
			fa[to][0]=x;
			dfs(to,x);
		}
	}
}
bool dfs1(int x,int ff){
	if(vis[x]) return 0;
	bool flag=0,ans=0;
	for(int i=hd[x];i;i=e[i].next){
		int to=e[i].to;
		if(to!=ff){
			flag=1;
			ans|=dfs1(to,x);
		} 
	}
	if(!flag) return 1;
	return ans;
}
struct tongyf{
	int x;
	bool operator < (const tongyf&a) const{
		return dep[x]<dep[a.x];
	}
};
bool check(int mid){
	multiset<tongyf> h;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=m;i++){
		w[i].now=w[i].pos;
		w[i].rest=mid;
		w[i].used=0;
	}
	sort(w+1,w+1+m,cmp);
	int pos=1;
    //先移动到不了根的
	for(int i=1;i<=m&&dep[w[i].pos]>mid;i++){
		int rest=mid,now=w[i].pos;
		for(int j=19;j>=0;j--){
			if(dep[now]-dep[fa[now][j]]<=rest){
				rest-=dep[now]-dep[fa[now][j]];
				now=fa[now][j];
			}
		}
		w[i].rest=0;
		w[i].now=now;
		vis[now]=1;
		w[i].used=1;
		pos++;
	}
    //看哪个儿子包含没有被覆盖的叶子
	for(int i=hd[1];i;i=e[i].next){
		int to=e[i].to;
		if(dfs1(to,1)==1){
			h.insert((tongyf){to});
		}
	}
    //对于没法去根并且回来的就呆在原地
	for(int i=pos;i<=m;i++){
		int rest=mid,now=w[i].pos;
		for(int j=19;j>=0;j--){
			if(dep[fa[now][j]]>dep[1]&&dep[now]-dep[fa[now][j]]<=rest){
				rest-=dep[now]-dep[fa[now][j]];
				now=fa[now][j];
			}
		}
		w[i].rest=rest;
		w[i].now=now;
		if(2*l[now]>rest){
			h.erase((tongyf){now});
			w[i].used=1;
			vis[now]=1;
		}
	}
	sort(w+1,w+1+m,cmp1);
	int p=1;
	while(w[p].used==0&&p<=m) p++;
	p--;
    //让军队驻扎剩下的有未覆盖的叶子的儿子
	for(int i=1;i<=p;i++){
		if(h.empty()) return 1;
		int val=w[i].rest-dep[w[i].now];
		tongyf kkk;
		tongyf now=*h.begin();
		if(dep[now.x]<=val){
			kkk=now;
			vis[now.x]=1;
		}
		h.erase(kkk);
	}
	if(h.empty()) return 1;
	return 0;
}
signed main(){
	n=read();
	for(int i=1;i<n;i++){
		int x=read(),y=read(),z=read();
		addedge(x,y,z);
		addedge(y,x,z);
	}
	memset(dep,-127,sizeof(dep));
	dep[1]=0;
	dfs(1,0);
	m=read();
	for(int i=1;i<=m;i++){
		w[i].pos=read();
	}
	int hd=0,tl=1e15,ans=1e15;
	while(hd<=tl){
		int mid=(hd+tl)/2;
		if(check(mid)){
			ans=mid;
			tl=mid-1;
		}
		else hd=mid+1;
	}
	if(ans>=1e15) puts("-1");
	else printf("%lld\n",ans);
	return 0;
}