| 比赛 |
寒假集训5 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
白色相簿的季节 |
最终得分 |
100 |
| 用户昵称 |
LikableP |
运行时间 |
0.904 s |
| 代码语言 |
C++ |
内存使用 |
8.48 MiB |
| 提交时间 |
2026-03-01 11:32:08 |
显示代码纯文本
#include <cstdio>
#include <queue>
#include <cstring>
const int MAXN = 1e5 + 10;
struct EDGE {
int v, w, next;
} edge[MAXN << 1];
int head[MAXN], edgeNum;
void AddEdge(int u, int v, int w) {
edge[++edgeNum] = {v, w, head[u]};
head[u] = edgeNum;
}
int n, q, k;
bool vis[MAXN];
int dis[MAXN];
std::priority_queue<std::pair<int, int>> pq;
void Dijkstra() {
memset(dis, 0x3f, sizeof(dis));
for (int i = 1, keypoint; i <= k; ++i) {
scanf("%d", &keypoint);
dis[keypoint] = 0;
pq.emplace(-dis[keypoint], keypoint);
}
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = head[u]; i; i = edge[i].next) {
int v= edge[i].v, w = edge[i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
pq.emplace(-dis[v], v);
}
}
}
}
int siz[MAXN], fa[MAXN], son[MAXN], depth[MAXN];
void FindHeavy(int u, int fa) {
siz[u] = 1, ::fa[u] = fa, depth[u] = depth[fa] + 1;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (v == fa) continue;
FindHeavy(v, u);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
int pos[MAXN], pcnt, rank[MAXN], top[MAXN];
void ConnectHeavy(int u, int ancester) {
pos[u] = ++pcnt, rank[pcnt] = u, top[u] = ancester;
if (son[u]) ConnectHeavy(son[u], ancester);
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (v == fa[u] || v == son[u]) continue;
ConnectHeavy(v, v);
}
}
int disToRoot[MAXN];
void CalcDistanceToRoot(int u, int fa) {
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v, w = edge[i].w;
if (v == fa) continue;
disToRoot[v] = disToRoot[u] + w;
CalcDistanceToRoot(v, u);
}
}
struct NODE {
int minn;
} node[MAXN << 2];
#define ls(root) root << 1
#define rs(root) root << 1 | 1
void PushUp(int root) {
node[root].minn = std::min(node[ls(root)].minn, node[rs(root)].minn);
}
void Build(int root, int lt, int rt) {
if (lt == rt) {
node[root].minn = dis[rank[lt]];
return ;
}
int mid = lt + ((rt - lt) >> 1);
Build(ls(root), lt, mid);
Build(rs(root), mid + 1, rt);
PushUp(root);
}
int GetSeqMin(int root, int lt, int rt, int lq, int rq) {
if (lt == lq && rt == rq) {
return node[root].minn;
}
int mid = lt + ((rt - lt) >> 1);
if (rq <= mid) {
return GetSeqMin(ls(root), lt, mid, lq, rq);
} else if (lq > mid) {
return GetSeqMin(rs(root), mid + 1, rt, lq, rq);
} else {
return std::min(GetSeqMin(ls(root), lt, mid, lq, mid), GetSeqMin(rs(root), mid + 1, rt, mid + 1, rq));
}
}
int GetDistance(int x, int y) {
if (depth[x] > depth[y]) std::swap(x, y);
return disToRoot[y] - disToRoot[x];
}
int GetPathMin(int x, int y) {
int minn = 0x7fffffff, lockx = x, locky = y, lca = 0;
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]]) std::swap(x, y);
minn = std::min(minn, GetSeqMin(1, 1, n, pos[top[x]], pos[x]));
x = fa[top[x]];
}
if (depth[x] > depth[y]) std::swap(x, y);
lca = x;
minn = std::min(minn, GetSeqMin(1, 1, n, pos[x], pos[y]));
return minn * 2 + GetDistance(lockx, lca) + GetDistance(locky, lca);
}
int main() {
#ifdef LOCAL
freopen("!input.in", "r", stdin);
freopen("!output.out", "w", stdout);
#else
freopen("wa.in", "r", stdin);
freopen("wa.out", "w", stdout);
#endif
scanf("%d %d %d", &n, &q, &k);
for (int i = 1, u, v, w; i <= n - 1; ++i) {
scanf("%d %d %d", &u, &v, &w);
AddEdge(u, v, w);
AddEdge(v, u, w);
}
Dijkstra();
FindHeavy(1, 0);
ConnectHeavy(1, 1);
CalcDistanceToRoot(1, 0);
Build(1, 1, n);
for (int s, t; q--;) {
scanf("%d %d", &s, &t);
printf("%d\n", GetPathMin(s, t));
}
return 0;
}