比赛 寒假集训5 评测结果 AAAAAAAAAA
题目名称 白色相簿的季节 最终得分 100
用户昵称 123 运行时间 2.038 s
代码语言 C++ 内存使用 19.21 MiB
提交时间 2026-03-01 09:16:59
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10,K=22;
int n,k,a[N],head[N],idx[M],nxt[M],val[M],tot=0,dis[N],vis[N],f[N][K],d[N][K],e,depth[N],w[N][K];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int> > > q;
void add(int x,int y,int z)
{
    idx[++tot]=y;
    val[tot]=z;
    nxt[tot]=head[x];
    head[x]=tot;
}
void dijkstra()
{
    memset(dis,0x3f,sizeof(dis));
    for (int i=1;i<=k;i++)
    {
        q.push({0,a[i]});
        dis[a[i]]=0;
    }
    while (!q.empty())
    {
        int t=q.top().second;q.pop();
        if (vis[t]) continue;
        vis[t]=1;
        for (int i=head[t];i;i=nxt[i])
        {
            int y=idx[i];
            if (dis[y]>dis[t]+val[i])
            {
                dis[y]=dis[t]+val[i];
                if (!vis[y]) q.push({dis[y],y});
            }
        }
    }
}
void dfs(int now,int fa)
{
    f[now][0]=fa,d[now][0]=min(dis[now],dis[fa]),depth[now]=depth[fa]+1;
    for (int i=1;i<=20;i++) f[now][i]=f[f[now][i-1]][i-1],d[now][i]=min(d[now][i-1],d[f[now][i-1]][i-1]),w[now][i]=w[now][i-1]+w[f[now][i-1]][i-1];
    for (int i=head[now];i;i=nxt[i])
    {
        int y=idx[i];
        if (y==fa) continue;
        w[y][0]=val[i];
        dfs(y,now);
    }
}
long long lca(int x,int y)
{
    if (depth[x]<depth[y]) swap(x,y);
    long long mi=min(2ll*dis[x],2ll*dis[y]),ans=0;
    for (int i=20;i>=0;i--)
    {
        if (depth[f[x][i]]>=depth[y])
        {
            ans+=w[x][i];
            mi=min(mi,2ll*d[x][i]);
            x=f[x][i];
        }
    }
    if (x==y) return mi+ans;
    for (int i=20;i>=0;i--)
    {
        if (f[x][i]!=f[y][i])
        {
            ans+=w[x][i]+w[y][i];
            mi=min(mi,min(2ll*d[x][i],2ll*d[y][i]));
            x=f[x][i],y=f[y][i];
        }
    }
    ans+=w[x][0]+w[y][0];
    mi=min(mi,min(2ll*d[x][0],2ll*d[y][0]));
    return ans+mi;
}
int main() {
    freopen("wa.in","r",stdin);
    freopen("wa.out","w",stdout);
    cin>>n>>e>>k;
    for (int i=1;i<n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z),add(y,x,z);
    }
    for (int i=1;i<=k;i++) cin>>a[i];
    dijkstra();
    dfs(1,0);
    while (e--)
    {
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<endl; 
    }
}