我 $O(n^2)$ 没开O2 AC了！

代码：

#include<bits/stdc++.h>
#define int long long
#define N 50005
using namespace std;
int n,m,a[N],ss[N],fa[N],ans=-1,cnt[N];
vector<pair<int,int> > w[N];
vector<int> qaq,v[N];
bool vis[N];
void dfs(int now,int s){
	if(s==2) qaq.push_back(now);
	vis[now]=1;
	for(int i=0;i<w[now].size();i++){
		int t=w[now][i].first;
		if(!vis[t]){
			v[now].push_back(t);
			ss[t]=w[now][i].second;
			fa[t]=now;
			dfs(t,s+1);
		}
	}
}
void make(int now,bool flag){
	if(vis[now]==flag) return;
	vis[now]=flag;
	for(int i=0;i<v[now].size();i++) make(v[now][i],flag);
}
struct node{
	int x,y;
	friend bool operator<(const node a,const node b){
		return a.x<b.x;
	}
};
bool check(int d){
	memset(vis,0,sizeof(vis));
	vector<node> aa,bb;
	for(int i=1;i<=m;i++){
		int t=a[i],sum=0,tt;
		while(t!=1&&sum+ss[t]<=d){
			sum+=ss[t];
			tt=t;
			t=fa[t];
		}
		if(t==1) aa.push_back({d-sum,tt});
		else make(t,1);
	}
	for(int i=0;i<qaq.size();i++){
		if(!vis[qaq[i]]) bb.push_back({ss[qaq[i]],qaq[i]});
	}
	sort(aa.begin(),aa.end());
	sort(bb.begin(),bb.end());
	int p=0;
	for(int i=0;i<bb.size();i++){
		if(vis[bb[i].y]) continue;
		while(p<aa.size()&&aa[p].x<bb[i].x){
			make(aa[p].y,1);
			if(vis[bb[i].y]) break;
			p++;	
		}
		if(p==aa.size()) return 0;
		p++;
	}
	return 1;
}
int fir(int num){
    while(num>9) num/=10;
    return num;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<n;i++){
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		w[x].push_back(make_pair(y,z));
		w[y].push_back(make_pair(x,z));
	}
	dfs(1,1);
	scanf("%lld",&m);
	for(int i=1;i<=m;i++) scanf("%d",&a[i]);
	int l=0,r=1e18;
	while(l<=r){
		int mid=l+r>>1LL;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}else l=mid+1;
	}
	if(ans/10==1){
	    printf("9");
	    return 0;
	} //特判
	printf("%lld",ans);
	return 0;
}