比赛 寒假集训5 评测结果 AAAAAAAAAA
题目名称 白色相簿的季节 最终得分 100
用户昵称 李金泽 运行时间 0.883 s
代码语言 C++ 内存使用 24.79 MiB
提交时间 2026-03-01 09:26:55
显示代码纯文本
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 100005
#define int long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int n,m,k,h[N],cnt,d[N],dp[N],dep[N],fa[N][21],g[N][21],ans,op,x,y,z;
const int inf=1e18;
bool b[N];
struct node{int u,w;bool operator<(node y)const{return w>y.w;}};
struct edge{int v,n,w;}e[N<<1];
void ad(int u,int v,int w){e[++cnt]={v,h[u],w};h[u]=cnt;}
priority_queue<node>q;
void swap(int &x,int &y){int t=x;x=y;y=t;}
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
void dfs(int u,int f)
{
    dp[u]=dp[fa[u][0]=f]+1;
    g[u][0]=min(d[u],f?d[f]:inf);
    for(int i=h[u];i;i=e[i].n)
    {
        int v=e[i].v,w=e[i].w;
        if(v!=f)dep[v]=dep[u]+w,dfs(v,u);
    }
}
void init()
{
    fo(k,1,20)
        fo(i,1,n)
            fa[i][k]=fa[fa[i][k-1]][k-1],
            g[i][k]=min(g[i][k-1],g[fa[i][k-1]][k-1]);
}
node lca(int x,int y)
{
    int ans=min(d[x],d[y]);
    if(dp[x]<dp[y])swap(x,y);
    rf(k,20,0)
        if(fa[x][k]&&dp[fa[x][k]]>=dp[y])
            ans=min(ans,g[x][k]),x=fa[x][k];
    if(x==y)return {x,ans};
    rf(k,20,0)
        if(fa[x][k]^fa[y][k])
            ans=min(ans,min(g[x][k],g[y][k])),x=fa[x][k],y=fa[y][k];
    return {fa[x][0],min(ans,min(g[x][0],g[y][0]))};
}
int read(){
    int sum=0;bool f=0;char c=getchar();
    for(;c<48||c>57;c=getchar())if(c==45)f=1;
    for(;c>=48&&c<=57;c=getchar())sum=sum*10+(c&15);
    return f?-sum:sum;
}
signed main(){
    freopen("wa.in","r",stdin);freopen("wa.out","w",stdout);
    memset(d,0x3f,sizeof(d));
    n=read();m=read();k=read();
    fo(i,1,n-1)x=read(),y=read(),z=read(),ad(x,y,z),ad(y,x,z);
    fo(i,1,k)x=read(),d[x]=0,q.push({x,0});
    while(q.size())
    {
        node u=q.top();q.pop();
        if(b[u.u])continue;
        b[u.u]=1;
        for(int i=h[u.u];i;i=e[i].n)
        {
            int v=e[i].v,w=u.w+e[i].w;
            if(w<d[v])
            {
                d[v]=w;
                q.push({v,w});
            }
        }
    }
    dfs(1,0);init();
    while(m--)
    {
        x=read();y=read();
        node u=lca(x,y);
        printf("%lld\n",dep[x]+dep[y]-2*dep[u.u]+2*u.w);
    }
    return 0;
}