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