比赛 寒假集训5 评测结果 AAAAAAAAAA
题目名称 白色相簿的季节 最终得分 100
用户昵称 我常常追忆未来 运行时间 3.001 s
代码语言 C++ 内存使用 60.30 MiB
提交时间 2026-03-01 09:46:16
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
struct node{
    int l,r,minn;
}t[2*N];
struct edge{
    int to,val;
};
vector<edge>g[N];
vector<int>G[N];
int cnt,root,tot,n,q,k;
int dis[N],siz[N],son[N],top[N],dep[N],id[N],at[N],f[N],vis[N],to_root[N];
void pushup(int p){
    t[p].minn=min(t[t[p].l].minn,t[t[p].r].minn);
}
void build(int &p,int l,int r){
    p=++cnt;
    if(l==r){
    	t[p].minn=at[l];
    	return;	
    }
    int mid=l+r>>1;
    build(t[p].l,l,mid);
    build(t[p].r,mid+1,r);
    pushup(p);
}
int query(int p,int l,int r,int ql,int qr){
    if(l>qr||r<ql){
    	return 1e9;
    }
    if(ql<=l&&r<=qr){
    	return t[p].minn;
    }
    int mid=l+r>>1;
    return min(query(t[p].l,l,mid,ql,qr),query(t[p].r,mid+1,r,ql,qr));
}
void dfs1(int u,int fa){
   	siz[u]=1;
    dep[u]=dep[fa]+1;
    f[u]=fa;
    for(auto v:G[u]){
    	if(v!=fa){
    		dfs1(v,u);
    		siz[u]+=siz[v];
    		if(!son[u]||siz[son[u]]<siz[v]){
    			son[u]=v;
    		}
    	}
    }
}
void dfs2(int u,int topu){
    id[u]=++tot;
    at[tot]=dis[u];
    top[u]=topu;
    if(!son[u]){
    	return;
    }
    dfs2(son[u],topu);
    for(auto v:G[u]){
    	if(v!=f[u]&&v!=son[u]){
    		dfs2(v,v);
    	}
    }
}
void dfs3(int u,int fa){
    for(auto vv:g[u]){
    	int v=vv.to,val=vv.val;
    	if(v!=fa){
    		to_root[v]=to_root[u]+val;
    		dfs3(v,u);
    	}
    }
}
void dij(){
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pair<int,int> >q;
    for(int i=1;i<=k;i++){
    	int u;
    	cin>>u;
    	q.push({0,u});
    	dis[u]=0;
    }	
   	while(!q.empty()){
   		int u=q.top().second;
   		q.pop();
    	if(vis[u]){
    		continue;
   		}
    	vis[u]=1;
    	for(auto vv:g[u]){
    		int v=vv.to,val=vv.val;
    		if(dis[v]>dis[u]+val){
    			dis[v]=dis[u]+val;
    			q.push({-dis[v],v});
    		}
    	}
    }
}
int qmin(int x,int y){
    int ans=1e9,res=to_root[x]+to_root[y];
    while(top[x]!=top[y]){ 
    	if(dep[top[x]]<dep[top[y]]){
    		swap(x,y);
    	}
    	ans=min(query(root,1,n,id[top[x]],id[x]),ans);
    	x=f[top[x]]; 
    }
    if(dep[x]<dep[y]){
    	swap(x,y);
    }
    ans=min(ans,query(root,1,n,id[y],id[x]));	
    return (res-2*to_root[y]+ans*2);
} 
int main(){
    freopen("wa.in","r",stdin);
    freopen("wa.out","w",stdout);
    cin>>n>>q>>k;
    for(int i=1;i<n;i++){
    	int u,v,w;
    	cin>>u>>v>>w;
    	G[u].push_back(v);
    	G[v].push_back(u);
    	g[u].push_back({v,w});
    	g[v].push_back({u,w});
    }
    dij();
    dfs1(1,0);
    dfs2(1,1);
    dfs3(1,0);
    build(root,1,n);
    for(int i=1;i<=q;i++){
    	int s,t;
    	cin>>s>>t;
    	cout<<qmin(s,t)<<"\n";
    } 
   	return 0;
}