比赛 寒假集训5 评测结果 WWWWWAWWWW
题目名称 白色相簿的季节 最终得分 10
用户昵称 彭欣越 运行时间 0.980 s
代码语言 C++ 内存使用 24.51 MiB
提交时间 2026-03-01 12:58:34
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int n,q,k,a[N],vis[N],in[N];
ll d[N],dis[N],f[N][22],mk[N][22];
int head[N],tot;
struct edge {
    int v,nxt;
    ll w;
}e[N*2];
struct node {
    ll pos,dis;
    bool operator<(const node&o) const{
        return o.dis<dis;
    }
};
void add (int u,int v,ll w) {
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
ll LCA (int x,int y) {
    if (d[x]>d[y]) swap(x,y);
    for (int i=20;i>=0;i--) {
        if (d[f[y][i]]>=d[x]) y=f[y][i];
    }
    if (x==y) return x;
    for (int i=20;i>=0;i--) {
        if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    }
    if (x==1) return 1;
    return f[x][0];
}
bool check (int x,int y) {
    int ans=0;
    if (d[x]>d[y]) swap(x,y);
    for (int i=20;i>=0;i--) {
        if (d[f[y][i]]>=d[x]) {
            y=f[y][i];
            ans|=mk[y][i];
        }
    }
    //cout << x <<' '<< y <<' '<< ans <<endl;
    if (x==y) return ans;
    for (int i=20;i>=0;i--) {
        if (f[x][i]!=f[y][i]) {
            x=f[x][i],y=f[y][i];
            ans|=mk[x][i];
            ans|=mk[y][i];
        }
    }
    return ans|mk[x][0];
}
priority_queue<node>q1;
void bfs () {
    for (int i=1;i<=n;i++) dis[i]=1e18;
    for (int i=1;i<=n;i++) if (a[i]) q1.push({i,0}),dis[i]=0;
    while (!q1.empty()) {
        int u=q1.top().pos;
        q1.pop();
        if (vis[u]) continue;
        vis[u]=1;
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (dis[v]>dis[u]+e[i].w) {
                dis[v]=dis[u]+e[i].w;
                if (!vis[v]) q1.push({v,dis[v]});
            }
        }
    }
}
void dfs (int u,int fa) {
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==fa) continue;
        f[v][0]=u;
        mk[v][0]=a[u];
        d[v]=d[u]+e[i].w;
        dfs(v,u);
        for (int j=1;j<=20;j++) {
            f[v][j]=f[f[v][j-1]][j-1];
            mk[v][j]=(mk[f[v][j-1]][j-1]|mk[v][j-1]);
        }
    }
}
int main () {
    freopen("wa.in","r",stdin);
    freopen("wa.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0); 
    d[0]=-1e18;
    cin >> n >> q >> k;
    for (int i=1;i<n;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
        //in[b]++;
    }
    for (int i=1;i<=k;i++) {
        int x;
        cin >> x;
        a[x]=1;
    }
    f[0][0]=1;
    dfs(1,0);
    bfs();
    //cout << mk[7][0] <<' '<< d[7] <<' '<< d[1] <<endl;
    while (q--) {
        int x,y;
        cin >> x >> y;
        int t=LCA(x,y);
        if (check(x,y)||a[x]||a[y]) cout << d[x]+d[y]-2*d[t] <<"\n";
        else cout << d[x]+d[y]-2*d[t]+2*dis[t] <<"\n";
    }
    return 0; 
}