比赛 寒假集训5 评测结果 AAAAAAAATA
题目名称 白色相簿的季节 最终得分 90
用户昵称 KKZH 运行时间 2.631 s
代码语言 C++ 内存使用 45.95 MiB
提交时间 2026-03-01 10:05:56
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
const int M=21;
int n,q,k,cnt,f[N],head[N],dis[N],ok,mn,all,dep[N];
struct node{
    int nxt,to,wei;
}ed[N];
struct node1{
    int dis,to,yes,len;
}fa[N][30];
void add(int x,int y,int z){
    ed[++cnt].nxt=head[x];
    head[x]=cnt;
    ed[cnt].to=y;
    ed[cnt].wei=z;
}
void dfs(int x,int now,int tot,int fa){
    if(f[x]==1){
        dis[now]=min(tot,dis[now]);
        return;
    } 
    for(int i=head[x];i!=0;i=ed[i].nxt){
        int y=ed[i].to;
        if(y==fa) continue;
        if(y<now){
            dis[now]=min(dis[y]+tot+ed[i].wei,dis[now]);
        }else{
            dfs(y,now,ed[i].wei+tot,x);
        }
    }
}
void dfs1(int x,int fat,int lent){
    dep[x]=dep[fat]+1;
    fa[x][0].to=fat;
    fa[x][0].len=lent;
    fa[x][0].dis=min(dis[x],dis[fat]);
    fa[x][0].yes=(f[fat]|f[x]);
//    cout<<x<<endl;
//        cout<<fa[x][0].len<<" "<<fa[x][0].to<<" "<<fa[x][0].dis<<" "<<fa[x][0].yes<<endl;
    for(int i=1;i<=M;i++){
        fa[x][i].len=fa[fa[x][i-1].to][i-1].len+fa[x][i-1].len;
        fa[x][i].to=fa[fa[x][i-1].to][i-1].to;
        fa[x][i].dis=min(fa[fa[x][i-1].to][i-1].dis,fa[x][i-1].dis);
        fa[x][i].yes=(fa[fa[x][i-1].to][i-1].yes|fa[x][i-1].yes);
//        cout<<fa[x][i].len<<" "<<fa[x][i].to<<" "<<fa[x][i].dis<<" "<<fa[x][i].yes<<endl;
    }
    for(int i=head[x];i!=0;i=ed[i].nxt){
        int y=ed[i].to;
        if(y==fat) continue;
        dfs1(y,x,ed[i].wei);
    }
}
int LCA(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]){
        ok=(ok|fa[x][__lg(dep[x]-dep[y])].yes);
        all+=fa[x][__lg(dep[x]-dep[y])].len;
        mn=min(mn,fa[x][__lg(dep[x]-dep[y])].dis);
        x=fa[x][__lg(dep[x]-dep[y])].to;
    }
//    cout<<dep[x]<<"  "<<dep[y]<<endl;
    if(x==y) return x;
    for(int i=M;i>=0;i--){
        if(fa[x][i].to!=fa[y][i].to){
            all+=fa[x][i].len+fa[y][i].len;
            ok=(ok|(fa[x][i].yes|fa[y][i].yes));
            mn=min(mn,min(fa[x][i].dis,fa[y][i].dis));
            x=fa[x][i].to;
            y=fa[y][i].to;
//            cout<<mn<<" "<<all<<" "<<ok<<endl;
        }
    }
    all+=fa[x][0].len+fa[y][0].len;
    ok=(ok|(fa[x][0].yes|fa[y][0].yes));
    mn=min(mn,min(fa[x][0].dis,fa[y][0].dis));
    return fa[x][0].to;
}
signed main(){
	freopen("wa.in","r",stdin);
	freopen("wa.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin>>n>>q>>k;
    int x,y,z;
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<n;i++){
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1;i<=k;i++){
        cin>>x;
        f[x]=1;
    }
    for(int i=1;i<=n;i++)
        dfs(i,i,0,0);
    dfs1(1,0,0);
    for(int i=1;i<=q;i++){
        cin>>x>>y;
        if(x==y&&f[x]==1){
            cout<<0<<endl;
            continue;
        }
        if(x==y){
            cout<<dis[x]*2<<endl;
            continue;
        }
        ok=all=0;
        mn=INT_MAX;
        z=LCA(x,y);
        if(ok==1){
            cout<<all<<endl;
        }else{
            cout<<all+mn*2<<endl;
        }
    }
}