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