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