比赛 寒假集训5 评测结果 AAAAAAAAAA
题目名称 白色相簿的季节 最终得分 100
用户昵称 xuyuqing 运行时间 1.593 s
代码语言 C++ 内存使用 27.78 MiB
提交时间 2026-03-01 10:17:05
显示代码纯文本

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

const int N = 114514;
const int Log = 18;

int n;
int q;
int k;
vector<pair<int, long long>> graph[N];
bool sp[N];

long long nearSp[N];
bool vis[N];

int fa[N];
int dep[N];
long long dist[N];
int siz[N];
int heavy[N];
int grand[N];
int cc;
int dfn[N];
int org[N];

int log_2[N];
long long st[N][Log];

void dijkstra () {
    priority_queue<pair<long long, int>> pq;
    for (int i = 1; i <= n; i++) {
        if (sp[i]) {
            pq.emplace(0, i);
        }
        else {
            nearSp[i] = 1e18;
        }
    }
    
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i].first;
            long long dis = graph[u][i].second;
            
            if (nearSp[u] + dis < nearSp[v]) {
                nearSp[v] = nearSp[u] + dis;
                
                if (!vis[v]) {
                    pq.emplace(-nearSp[v], v);
                }
            }
        }
    }
} 

void dfs1 (int now, int dad) {
    int maxn = 0;
    siz[now] = 1;
    for (int i = 0; i < graph[now].size(); i++) {
        int son = graph[now][i].first;
        long long dis = graph[now][i].second;
        
        if (son == dad) {
            continue;
        }
        
        fa[son] = now;
        dep[son] = dep[now] + 1;
        dist[son] = dist[now] + dis;
        
        dfs1 (son, now);
        if (siz[son] > maxn) {
            maxn = siz[son];
            heavy[now] = son;
        }
        siz[now] += siz[son];
    }
}

void dfs2 (int now, int gra) {
    grand[now] = gra;
    cc++;
    dfn[now] = cc;
    org[cc] = now;
    
    if (heavy[now]) {
        dfs2 (heavy[now], gra);
    }
    
    for (int i = 0; i < graph[now].size(); i++) {
        int son = graph[now][i].first;
        long long dis = graph[now][i].second;
        
        if (son == fa[now] || son == heavy[now]) {
            continue;
        }
        
        dfs2 (son, son);
    }
}

void spareTable () {
    log_2[1] = 0;
    for (int i = 2; i <= n; i++) {
        log_2[i] = log_2[i >> 1] + 1;
    }
    
    memset (st, 0x3f, sizeof (st));
    for (int i = 1; i <= n; i++) {
        st[i][0] = nearSp[org[i]];
    }
    for (int i = 1; i < Log; i++) {
        for (int j = 1; j + (1 << (i - 1)) <= n; j++) {
            st[j][i] = min (st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
        }
    }
}

long long cal (int l, int r) {
    l = dfn[l];
    r = dfn[r];
    int num = log_2[r - l + 1];
    return min (st[l][num], st[r - (1 << num) + 1][num]);
}

void lca (int x, int y) {
    long long nowMin = 1e18;
    long long orgNum = dist[x] + dist[y];
    
    while (grand[x] != grand[y]) {
        if (dep[grand[x]] < dep[grand[y]]) {
            swap (x, y);
        }
        nowMin = min (nowMin, cal (grand[x], x));
        x = fa[grand[x]];
    }
    
    if (dep[x] > dep[y]) {
        swap (x, y);
    }
    
    nowMin = min (nowMin, cal (x, y));
    
    cout << nowMin * 2 + orgNum - 2 * dist[x] << endl;
}

int main () {
    
    freopen ("wa.in", "r", stdin);
    freopen ("wa.out", "w", stdout);
    
    scanf ("%d %d %d", &n, &q, &k);
    for (int i = 1; i < n; i++) {
        int u, v;
        long long w;
        scanf ("%d %d %lld", &u, &v, &w);
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }
    for (int i = 1; i <= k; i++) {
        int u;
        scanf ("%d", &u);
        sp[u] = true;
    }
    
    dijkstra ();
    dfs1 (1, 0);
    dfs2 (1, 1);
    spareTable ();
    
    for (int i = 1; i <= q; i++) {
        int s, t;
        scanf ("%d %d", &s, &t);
        lca (s, t);
    }
    
    return 0;
}