比赛 寒假集训5 评测结果 AAAAAAAAAA
题目名称 白色相簿的季节 最终得分 100
用户昵称 zhyn 运行时间 1.564 s
代码语言 C++ 内存使用 13.53 MiB
提交时间 2026-03-01 11:46:27
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define maxn 100005
#define inf 0x7f7f7f7f7f7f7f7f
#define smid int mid=(l+r)/2
int n,m;
struct node{
	int v;
	ll w;
};

struct edge{
	int v;
	ll w;
	friend bool operator<(edge a,edge b){
		return a.w>b.w;
	}
};

vector<node>e[maxn];
int num[maxn];
bool vis[maxn];
int f[maxn],siz[maxn],son[maxn],top[maxn],dep[maxn],dfn[maxn],id[maxn];
ll val[maxn];
ll dis[maxn];
int tot=0,k;
priority_queue<edge>q;
ll wd[maxn*4],wm[maxn*4];

void dij(){
	for(int i=1;i<=n;i++){
		dis[i]=inf;
		vis[i]=false;
	}
	for(int i=1;i<=k;i++){
		dis[num[i]]=0;
		q.push({num[i],0});
	}
	while(!q.empty()){
		int u=q.top().v;
		q.pop();
		if(vis[u]){
			continue;
		}
		vis[u]=true;
		for(node x:e[u]){
			int v=x.v;
			ll w=x.w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({v,dis[v]});
			} 
		}
	}
}

void dfs1(int u,int fa){
	f[u]=fa;
	dep[u]=dep[fa]+1;
	siz[u]=1;
	for(node x:e[u]){
		int v=x.v;
		ll w=x.w;
		if(v==fa){
			continue;
		}
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]){
			son[u]=v;
		}
		val[v]=w;
	}
}

void dfs2(int u,int t){
	dfn[u]=++tot;
	id[dfn[u]]=u;
	top[u]=t;
	if(!son[u]){
		return;
	}
	dfs2(son[u],t);
	for(node x:e[u]){
		int v=x.v;
		if(v==f[u]||v==son[u]){
			continue;
		}
		dfs2(v,v);
	}
}

void pushup(int u){
	wd[u]=wd[u*2]+wd[u*2+1];
	wm[u]=min(wm[u*2],wm[u*2+1]);
}

void build(int u,int l,int r){
	if(l==r){
		wm[u]=dis[id[l]];
		wd[u]=val[id[l]];
		return;
	}
	smid;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	pushup(u);
}

ll queryd(int u,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr){
		return wd[u];
	}
	smid;
	ll sum=0;
	if(ql<=mid){
		sum+=queryd(u*2,l,mid,ql,qr);
	}
	if(qr>mid){
		sum+=queryd(u*2+1,mid+1,r,ql,qr);
	}
	return sum;
}

ll querym(int u,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr){
		return wm[u];
	}
	smid;
	ll sum=inf;
	if(ql<=mid){
		sum=min(sum,querym(u*2,l,mid,ql,qr));
	}
	if(qr>mid){
		sum=min(sum,querym(u*2+1,mid+1,r,ql,qr));
	}
	return sum;
}


ll query_(int l,int r){
	ll sum=0,cnt=inf;
	while(top[l]!=top[r]){
		if(dep[top[l]]<dep[top[r]]){
			swap(l,r);
		}
		sum+=queryd(1,1,n,dfn[top[l]],dfn[l]);
		cnt=min(cnt,querym(1,1,n,dfn[top[l]],dfn[l]));
		l=f[top[l]];
	}
	if(dep[l]>dep[r]){
		swap(l,r);
	}
	if(l!=r){
		sum+=queryd(1,1,n,dfn[son[l]],dfn[r]);
	}
	cnt=min(cnt,querym(1,1,n,dfn[l],dfn[r]));
	return sum+cnt*2;
}

int main(){
	
	freopen("wa.in","r",stdin);
	freopen("wa.out","w",stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>k;
	
	for(int i=1;i<n;i++){
		int u,v;
		ll w;
		cin>>u>>v>>w;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	
	for(int i=1;i<=k;i++){
		cin>>num[i];
	}
	
	dfs1(1,0);
	dfs2(1,1);
	dij();
	build(1,1,n);
	
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		cout<<query_(u,v)<<"\n";
	}
	
	
	
	
	return 0;
}