比赛 寒假集训5 评测结果 AAAAAAAAAA
题目名称 白色相簿的季节 最终得分 100
用户昵称 exil 运行时间 1.211 s
代码语言 C++ 内存使用 36.91 MiB
提交时间 2026-03-01 11:28:37
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> v[100005][2];
int dian[100005];
int shen[100005];
int fa[100005];
int f[100005][40];
int len[100005];
int dis[100005];
int n,k,p;
int st[100005][20];
void chushihua(){
	int k = log2(n);
	for(int j = 1;j<=k;j++){
		for(int i = 1;i<=n;i++){
			f[i][j] = f[f[i][j-1]][j-1];
		}
	}
}
void chushihua2(){
	int k = log2(n);
	for(int j = 1;j<=k;j++){
		for(int i = 1;i<=n;i++){
			if(f[i][j]!=0)st[i][j] = min(st[f[i][j-1]][j-1],st[i][j-1]);
		}
	}
}
int pandeng(int y,int x){
	int k = log2(shen[y]);
	for(int i = k;i>=0;i--){
		if(shen[f[y][i]]>=shen[x])y = f[y][i];
	}
	return y;
}
int pandeng2(int y,int x){
	int k = log2(shen[y]);
	for(int i = k;i>=0;i--){
		if(shen[f[y][i]]>=shen[x])y = f[y][i];
	}
	return y;
}
int zui(int x,int y){
	int k = log2(shen[x]);
	for(int i = k;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int zui2(int x,int z){
	int k = log2(shen[x]);
	int ans=dis[x];
	
	for(int i = k;i>=0;i--){
		if(shen[f[x][i]]>=shen[z]){
		    ans=min(ans,st[x][i]);
			x = f[x][i];
		}
	}
	return ans;
}
signed main(){
    freopen("wa.in","r",stdin);
    freopen("wa.out","w",stdout);
    scanf("%lld%lld%lld",&n,&p,&k);
    for(int i = 1;i<n;i++){
        int u,vi,w;
        scanf("%lld%lld%lld",&u,&vi,&w);
        v[u][0].push_back(vi);
        v[vi][0].push_back(u);
        v[u][1].push_back(w);
        v[vi][1].push_back(w);
        dis[i]=-1;
    }
    dis[n]=-1;
    queue<int> qwq;
    for(int i = 1;i<=k;i++){
        int a;
        scanf("%lld",&a);
        dian[a]=1;
        qwq.push(a);
        dis[a]=0;
    }
    
    queue<int> q;
    q.push(1);
    shen[1]=1;
    
    while(!q.empty()){
        int d=q.front();
        for(int i = 0;i<v[d][0].size();i++){
            if(v[d][0][i]==fa[d])continue;
            fa[v[d][0][i]]=d;
            len[v[d][0][i]]=len[d]+v[d][1][i];
            q.push(v[d][0][i]);
            shen[v[d][0][i]]=shen[d]+1;
        }
        q.pop();
        
    }
    for(int i = 1;i<=n;i++)f[i][0]=fa[i];
    chushihua();
    
    if(k==n){
        
        for(int i = 1;i<=p;i++){
            int l,r;
            scanf("%lld%lld",&l,&r);
            
            int li=l,ri=r;
            
            if(shen[l]>shen[r])l=pandeng(l,r);
            else if(shen[l]<shen[r])r=pandeng(r,l);
            int g=0;
            if(l==r)g=l;
            else g=zui(l,r);
            printf("%lld\n",len[li]+len[ri]-len[g]*2);
            
        }
    }
    else {
        while(!qwq.empty()){
            int d=qwq.front();
            qwq.pop();
            for(int i = 0;i<v[d][0].size();i++){
                if(dis[v[d][0][i]]==-1){
                    dis[v[d][0][i]]=dis[d]+v[d][1][i];
                    qwq.push(v[d][0][i]);
                }
                else{
                    if(dis[v[d][0][i]]>dis[d]+v[d][1][i]){
                        dis[v[d][0][i]]=dis[d]+v[d][1][i];
                        qwq.push(v[d][0][i]);
                    }
                }
                
            }
            
        }
        for(int i = 1;i<=n;i++){
            if(fa[i]!=0)st[i][0]=min(dis[i],dis[fa[i]]);
            else st[i][0]=dis[i];
        }

        chushihua2();
//                for(int i = 1;i<=n;i++){
//            for(int j = 0;j<=10;j++)cout<<st[i][j]<<" ";
//            cout<<endl; 
//        }
        
        for(int i = 1;i<=p;i++){
            int l,r;
            scanf("%lld%lld",&l,&r);
            int li=l,ri=r;
            
            if(shen[l]>shen[r])l=pandeng(l,r);
            else if(shen[l]<shen[r])r=pandeng(r,l);
            int g=0;
            if(l==r)g=l;
            else g=zui(l,r);
            
            l=li,r=ri;
            int minn=0;
            minn=min(zui2(l,g),zui2(r,g));
            
            
            printf("%lld\n",min(len[li]+len[ri]-len[g]*2+minn*2,len[li]+len[ri]-len[g]*2+minn*2));
            
        }
        
        
       
    }
    
    
    
    return 0;
}