Luogu P4281 [AHOI2008]緊急集合 / 聚會

題目連結：​​傳送門​​

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
  int next, to;
}e[A];
int head[A], num;
void add(int fr, int to) {
  e[++num].next = head[fr];
  e[num].to = to;
  head[fr] = num;
}
int siz[A], dep[A], fa[A], top[A], son[A];
int n, m, a, b, c, lca1, lca2, lca3;
void prepare(int fr) {
  siz[fr] = 1;
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to;
    if (ca == fa[fr]) continue;
    fa[ca] = fr;
    dep[ca] = dep[fr] + 1;
    prepare(ca);
    siz[fr] += siz[ca];
    if (siz[ca] > siz[son[fr]]) son[fr] = ca;
  }
}
void dfs(int fr, int tp) {
  top[fr] = tp;
  if (son[fr]) dfs(son[fr], tp);
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to;
    if (ca == fa[fr] or ca == son[fr]) continue;
    dfs(ca, ca);
  }
}
int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    x = fa[top[x]];
  }
  return dep[x] < dep[y] ? x : y;
}
int depth() {
  return dep[a] + dep[b] + dep[c] - dep[lca1] - dep[lca2] - dep[lca3];
}

int main(int argc, char const *argv[]) {
  cin >> n >> m;
  for (int i = 2; i <= n; i++) scanf("%d%d", &a, &b), add(a, b), add(b, a);
  dep[1] = 1; prepare(1); dfs(1, 1);
  while (m--) {
    scanf("%d%d%d", &a, &b, &c);
    lca1 = lca(a, b), lca2 = lca(a, c), lca3 = lca(b, c);
    if (lca1 == lca2 and lca2 == lca3) printf("%d %d\n", lca1, depth());
    else if (lca1 == lca2) printf("%d %d\n", lca3, depth());
    else if (lca1 == lca3) printf("%d %d\n", lca2, depth());
    else if (lca2 == lca3) printf("%d %d\n", lca1, depth());
  }
  return 0;
}