比赛 寒假集训5 评测结果 AAAAAAAAAA
题目名称 白色相簿的季节 最终得分 100
用户昵称 ChenBp 运行时间 2.283 s
代码语言 C++ 内存使用 8.73 MiB
提交时间 2026-03-01 11:39:42
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <utility>
using namespace std;
const int N=2e5+5;
typedef long long ll;
int hd[N],nxt[N],to[N],vl[N],num=1;
void add(int u,int v,int w) {
	num++;
	to[num]=v;
	vl[num]=w;
	nxt[num]=hd[u];
	hd[u]=num;
}
int fa[N],dep[N],sz[N],son[N],dfn[N],top[N],c[N],rnk[N],tot=0;
void dfs1(int u,int f) {
	fa[u]=f;
	dep[u]=dep[f]+1;
	sz[u]=1;
	for(int i=hd[u]; i; i=nxt[i]) {
		int v=to[i];
		if(v==f) continue;
		c[v]=c[u]+vl[i];
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int ance) {
	dfn[u]=++tot;
	top[u]=ance;
	rnk[tot]=u;
	if(!son[u]) return;
	dfs2(son[u],ance);
	for(int i=hd[u]; i; i=nxt[i]) {
		int v=to[i];
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
        else y=fa[top[y]];
    }
    return (dep[x]<dep[y]?x:y);
}
int g[N];
int dis[N];
bool vis[N];

int tr[2*N];
#define mid ((l+r)/2)
#define lc (u*2)
#define rc (u*2+1)
void build(int u,int l,int r){
    if(l==r) {
        tr[u]=dis[rnk[l]];
        return;
    }
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[u]=min(tr[lc],tr[rc]);
}
int ask(int u,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return tr[u];
    }
    int res=0x7f7f7f7f;
    if(x<=mid) res=min(res,ask(lc,l,mid,x,y));
    if(mid+1<=y) res=min(res,ask(rc,mid+1,r,x,y));
    return res;
}
int main() {
    freopen("wa.in","r",stdin);
    freopen("wa.out","w",stdout);
	int n,q,k;
	cin>>n>>q>>k;
	for(int i=1; i<=n-1; i++) {
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	memset(dis,0x3f,sizeof(dis));
	priority_queue<pair<int,int>>p;
	for(int i=1; i<=k; i++) {
		cin>>g[i];
	    dis[g[i]]=0;
	    p.push(make_pair(0,g[i]));
	}
	while(!p.empty()) {
		int u=p.top().second;
		p.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=hd[u]; i; i=nxt[i]) {
			int v=to[i];
			if(dis[v]>dis[u]+vl[i]) {
				dis[v]=dis[u]+vl[i];
				p.push(make_pair(-dis[v],v));
			}
		}
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	while(q--){
	    int s,t;
	    cin>>s>>t;
	    int l=lca(s,t);
        ll ans=c[s]-c[l]+c[t]-c[l];
        int res=0x7f7f7f7f;
        while(top[s]!=top[t]){
            if(dep[top[s]]<dep[top[t]]) swap(s,t);
            res=min(res,ask(1,1,n,dfn[top[s]],dfn[s]));
            s=fa[top[s]];
        }
        if(dep[s]>dep[t]) swap(s,t);
        res=min(res,ask(1,1,n,dfn[s],dfn[t]));
        cout<<ans+2ll*res<<endl;
    }
	return 0;
}