比赛 寒假集训5 评测结果 AAAAAAAAAA
题目名称 白色相簿的季节 最终得分 100
用户昵称 Yis 运行时间 0.836 s
代码语言 C++ 内存使用 31.02 MiB
提交时间 2026-03-01 12:58:22
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100050;
long long st[maxn][18],stv[maxn][18],fa[maxn],fav[maxn],dep[maxn],stm[maxn][18];
long long head[maxn],nxt[2*maxn],val[2*maxn],to[2*maxn],cnt=0;
void addedge(long long u,long long v,long long w){
	cnt++;
	to[cnt]=v;
	val[cnt]=w;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
long long n,q,k,iskey[maxn],keycnt[maxn],minkey[maxn],minkey2[maxn];
void dfs1(long long now,long long last){
	if(head[now]==0){
		if(iskey[now]){
			minkey[now]=0;
			keycnt[now]=1;
			minkey2[now]=0;
		} 
	}else{
		if(iskey[now]){
			minkey2[now]=0;
			minkey[now]=0;
			keycnt[now]=1;
		} 
		long long ed=head[now];
		while(ed){
			if(to[ed]!=last){
			dep[to[ed]]=dep[now]+1;
			dfs1(to[ed],now);
			fav[to[ed]]=val[ed];
			fa[to[ed]]=now;
			if(keycnt[to[ed]]){
				minkey[now]=min(minkey[now],minkey[to[ed]]+val[ed]);
				keycnt[now]+=keycnt[to[ed]];
			}
			}
			ed=nxt[ed];
		}
	}
}
void build(){
	for(long long i=1;i<=n;i++){
		st[i][0]=i;
		st[i][1]=fa[i];
		stv[i][0]=0;
		stv[i][1]=fav[i];
	}
	for(long long log=2;log<18;log++){
		for(long long i=1;i<=n;i++){
			if(dep[i]>=1<<log){
				st[i][log]=st[fa[st[i][log-1]]][log-1];
				stv[i][log]=stv[i][log-1]+fav[st[i][log-1]]+stv[fa[st[i][log-1]]][log-1];
			}
		}
	}
}
long long cost=0;
long long glog2(long long n){
	long long h=0,t=n;
	while(t>1){
		t=t>>1;
		h++;
	}
	return h;
}
long long todep(long long ind,long long depth){
	if(dep[ind]==depth)return ind;
	long long i=dep[ind]-depth+1;
	long long t=glog2(i);
	cost+=stv[ind][t];
	return todep(st[ind][t],depth);
}
long long lca(long long a,long long b){
	if(dep[a]<dep[b])return lca(b,a);
	if(a==b)return b;
	a=todep(a,dep[b]);
	if(a==b)return b;
	while(1){
		if(a==b)return a;
		if(fa[a]==fa[b]){
			cost+=fav[a]+fav[b];
			return fa[a];
		}
		
		for(long long i=18;i-->0;){
			if(1<<i<=dep[a]&&st[a][i]!=st[b][i]){
				cost+=stv[a][i]+stv[b][i];
				a=st[a][i];
				b=st[b][i];
			}
		}
	}
}
void dfs2(long long now,long long last){
	if(head[now]==0)return ;
	long long ed=head[now];
	while(ed){
		if(to[ed]!=last){
		minkey2[to[ed]]=min(minkey[to[ed]],minkey2[now]+val[ed]);
		dfs2(to[ed],now);	
		}
		ed=nxt[ed];
	}
}
void build2(){
	for(long long i=1;i<=n;i++){
		stm[i][0]=minkey2[i];
		stm[i][1]=min(minkey2[i],minkey2[fa[i]]);
	}
	for(long long log=2;log<18;log++){
		for(long long i=1;i<=n;i++){
			if(dep[i]>=1<<log){
				stm[i][log]=min(stm[i][log-1],stm[fa[st[i][log-1]]][log-1]);
			}
		}
	}
}
long long findstm(long long a,long long b){
	if(a==b)return minkey2[b];
	long long i=dep[a]-dep[b]+1;
	long long t=glog2(i);
	if(1<<t!=i)
	return min(stm[a][t],findstm(fa[st[a][t]],b));
	else return stm[a][t];
}
long long quest(long long s,long long t){
	cost=0;
	long long l=lca(s,t);
	return cost+2*min(findstm(s,l),findstm(t,l));
}
int main(){
	freopen("wa.in","r",stdin);
	freopen("wa.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q>>k;
	long long u,v,w;
	for(long long i=0;i<maxn;i++){
		minkey[i]=1<<30;
		minkey2[i]=1<<30;
	}
	for(long long i=0;i<n-1;i++){
		cin>>u>>v>>w;
		addedge(u,v,w);
		addedge(v,u,w);
	}
	long long key=0;
	for(long long i=0;i<k;i++){
		cin>>key;
		iskey[key]=1;
	}
	
	dep[1]=1;
	dfs1(1,0);
	build();
	minkey2[1]=minkey[1];
	dfs2(1,0);
	build2();
	long long s,t;
	while(q--){
		cin>>s>>t;
		cout<<quest(s,t)<<'\n';
	}
	cout.flush();
	return 0;
}