比赛 寒假集训5 评测结果 AAAAAAAAAA
题目名称 白色相簿的季节 最终得分 100
用户昵称 终焉折枝 运行时间 1.029 s
代码语言 C++ 内存使用 18.21 MiB
提交时间 2026-03-01 10:35:58
显示代码纯文本
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 5;
const int LOG = 20;
const ll INF = 1e18;
int n, q, k, dep[MAXN], f[MAXN][LOG];
ll dis[MAXN], D[MAXN], minx[MAXN][LOG];
struct Edge{int to, nxt, len;}e[MAXN << 1];
int h[MAXN], tot;
void add(int u, int v, int w){
	e[++ tot] = {v, h[u], w};
	h[u] = tot;
}

struct Node {
    ll d; int u;
    bool operator > (const Node& b) const { return d > b.d; }
};

void dijkstra(){
    priority_queue<Node, vector<Node>, greater<Node> > pq;
    for(int i = 1;i <= n;i ++) if (D[i] == 0) pq.push({0, i});
    while(!pq.empty()){
        Node t = pq.top(); pq.pop();
        if(t.d > D[t.u]) continue;
        for(int i = h[t.u];i;i = e[i].nxt){
            int v = e[i].to;
            if(D[v] > D[t.u] + e[i].len){
                D[v] = D[t.u] + e[i].len;
                pq.push({D[v], v});
            }
        }
    }
}

void dfs(int u, int fa){
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    minx[u][0] = D[u];
    for(int i = h[u]; i; i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        dis[v] = dis[u] + e[i].len;
        dfs(v, u);
    }
}

void init(){
    for(int j = 1;j < LOG;j ++){
    	for(int i = 1; i <= n;i ++){
            f[i][j] = f[f[i][j - 1]][j - 1];
            minx[i][j] = min(minx[i][j - 1], minx[f[i][j - 1]][j - 1]);
        }
	}
}

int LCA(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int j = LOG - 1;j >= 0;j --)
		if(dep[f[u][j]] >= dep[v]) u = f[u][j];
    if(u == v) return u;
    for(int j = LOG - 1;j >= 0;j --)
        if(f[u][j] != f[v][j]) u = f[u][j], v = f[v][j];
    return f[u][0];
}

ll ask(int u, int v){
    int lca = LCA(u, v);
    ll res = min(D[u], D[v]);
    auto up = [&](int& cur){
        for(int j = LOG - 1;j >= 0;j --)
            if(dep[f[cur][j]] >= dep[lca]){
                res = min(res, minx[cur][j]);
                cur = f[cur][j];
            }
    };
    up(u); up(v);
    return min(res, D[lca]);
}

int main(){
	freopen("wa.in", "r", stdin);
	freopen("wa.out", "w", stdout);
    ios::sync_with_stdio(0);
	cin.tie(0);
    cin >> n >> q >> k;
    for(int i = 1, u, v, w;i < n;i ++){
        cin >> u >> v >> w;
        add(u, v, w); add(v, u, w);
    }
    fill(D, D + n + 1, INF);
    for(int i = 1, x;i <= k;i ++){cin >> x;D[x] = 0;}
    dijkstra();
    dfs(1, 0);
    init();
    while(q --){
        int u, v; cin >> u >> v;
        int lca = LCA(u, v);
        ll d = dis[u] + dis[v] - 2 * dis[lca];
        cout << d + 2 * ask(u, v) << "\n";
    }
    return 0;
}