比赛 寒假集训5 评测结果 AAAAAAAAAA
题目名称 白色相簿的季节 最终得分 100
用户昵称 PXCZM 运行时间 0.900 s
代码语言 C++ 内存使用 20.36 MiB
提交时间 2026-03-01 09:47:24
显示代码纯文本
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,q,k;
vector<pair<int,int> >a[100010];
int kk[100010];
ll d[100010],val[100010];
priority_queue<pair<ll,int> >p;
bool vis[100010];
struct node
{
    int fa,dep,son,siz,dfn,top;
    ll sum;
    node(){fa=dep=son=siz=dfn=top=sum=0;}
}z[100010];
void dfs1(int rt,int fa,int deep)
{
    z[rt].fa=fa;
    z[rt].dep=deep;
    z[rt].siz=1;
    int len=a[rt].size(),maxson=0;
    for(int i=0;i<len;i++)
    {
        int to=a[rt][i].second;
        if(to==fa)
        {
            z[rt].sum=a[rt][i].first;
            continue;
        }
        dfs1(to,rt,deep+1);
        z[rt].siz+=z[to].siz;
        if(z[to].siz>maxson)
        {
            maxson=z[to].siz;
            z[rt].son=to;
        }
    }
}
int cnt;
void dfs2(int rt,int topf)
{
    z[rt].dfn=++cnt;
    z[rt].top=topf;
    val[cnt]=d[rt];
    int len=a[rt].size();
    for(int i=0;i<len;i++)
    {
        int to=a[rt][i].second;
        if(to==z[rt].fa)
        {
            z[rt].sum+=z[to].sum;
            break;
        }
    }
    if(z[rt].son) dfs2(z[rt].son,topf);
    for(int i=0;i<len;i++)
    {
        int to=a[rt][i].second;
        if(to==z[rt].son||to==z[rt].fa) continue;
        dfs2(to,to);
    }
}
ll f[100010][20];
void ST()
{
    for(int i=1;i<=n;i++) f[i][0]=val[i];
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
ll query(int x,int y)
{
    int tmp=log2(y-x+1);
    return min(f[x][tmp],f[y-(1<<tmp)+1][tmp]);
}
void solve(int x,int y)
{
    ll ans=0,minn=1e18;
    int topx=z[x].top,topy=z[y].top;
    while(topx!=topy)
    {
        if(z[topx].dep<z[topy].dep)
        {
            swap(topx,topy);
            swap(x,y);
        }
        minn=min(minn,query(z[topx].dfn,z[x].dfn));
        ans+=z[x].sum-z[z[topx].fa].sum;
        x=z[topx].fa;
        topx=z[x].top;
    }
    if(z[x].dep>z[y].dep) swap(x,y);
    minn=min(minn,query(z[x].dfn,z[y].dfn));
    ans+=z[y].sum-z[x].sum;
    cout<<ans+minn<<'\n';
}
int main()
{
    freopen("wa.in","r",stdin);
    freopen("wa.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>q>>k;
    for(int i=1;i<n;i++)
    {
        int u,v,w;cin>>u>>v>>w;
        a[u].push_back(make_pair(w,v));
        a[v].push_back(make_pair(w,u));
    }
    for(int i=1;i<=n;i++) d[i]=1e17;
    for(int i=1;i<=k;i++)
    {
        cin>>kk[i];
        d[kk[i]]=0;
        p.push(make_pair(0,kk[i]));
    }
    while(p.size())
    {
        int h=p.top().second;
        p.pop();
        if(vis[h]) continue;
        vis[h]=1;
        int len=a[h].size();
        for(int i=0;i<len;i++)
        {
            ll w=a[h][i].first*2;
            int to=a[h][i].second;
            if(d[to]>d[h]+w)
            {
                d[to]=d[h]+w;
                p.push(make_pair(-d[to],to));
            }
        }
    }
    dfs1(1,0,1);
    dfs2(1,1);
    ST();
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        solve(x,y);
    }
    return 0;
}