| 比赛 |
寒假集训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;
}