比赛 寒假集训5 评测结果 AAAAATTATA
题目名称 白色相簿的季节 最终得分 70
用户昵称 dbk 运行时间 4.499 s
代码语言 C++ 内存使用 12.24 MiB
提交时间 2026-03-01 09:56:50
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, T = log2(100000) + 2;;
int f[N], sum[N], dep[N], n, q, K, ds, x[N], ans, up[N][T];
bool ff, k[N];
vector<pair<int, int> >g[N];

void dfs(int u, int fa, int w){
    f[u] = fa;
    dep[u] = dep[fa] + 1;
    sum[u] = sum[fa] + w;
    up[u][0] = fa;
	for(int i = 1;i < T;i++){
		up[u][i] = up[up[u][i - 1]][i - 1];
	}
    for(auto it : g[u]){
        if(it.first == fa) continue ;
        dfs(it.first, u, it.second);
    }
}

int lca(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	for(int i = T - 1;i >= 0;i--){
		if(dep[up[u][i]] >= dep[v]){
			u = up[u][i]; 
		} 
	} 
	if(u == v) return v;
	for(int i = T - 1;i >= 0;i--){
		if(up[u][i] != up[v][i]){
			u = up[u][i], v = up[v][i]; 
		} 
	} 
	return up[u][0]; 
}
bool check_key(int u, int v) {
    if (u == v) return k[u];
    int l = lca(u, v);
    int tmp = u;
    while (tmp != l) {
        if (k[tmp]) return 1;
        tmp = f[tmp];
    }
    if (k[l]) return 1;
    tmp = v;
    while (tmp != l) {
        if (k[tmp]) return 1;
        tmp = f[tmp];
    }
    return 0;
}
int main(){
    freopen("wa.in", "r", stdin);
    freopen("wa.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q >> K;
    for(int i = 1;i < n;i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    for(int i = 1;i <= K;i++){
        cin >> x[i];
        k[x[i]] = 1;
    }
    dfs(1, 0, 0);
    while(q--){
        ff = 0;
        int s, t, cs, ct;
        cin >> s >> t;
        cs = s, ct = t;
        ff = check_key(s, t);
        int l = lca(cs, ct);
        ans = sum[cs] + sum[ct] - 2 * sum[l];
        
        if(ff){
            cout<<ans<<endl;
        }
        else{
            int mi = INT_MAX;
            for(int i = 1;i <= K;i++){
                int dis = (sum[cs] + sum[x[i]] - 2 * sum[lca(cs, x[i])]) + (sum[ct] + sum[x[i]] - 2 * sum[lca(ct, x[i])]);
                mi = min(mi, dis);
            }
            cout<<mi<<endl;
        }
    }
    return 0;
}