under 题解 SP913

---

找树剖题的时候发现这题，发现用倍增很水简单，于是写了一发，发现跟现有题解还不大一样，于是写篇题解造 (bao) 福 (fu) 社会。

---

前置芝士

树上倍增，LCA

当然你也可以顺手树剖维护个 LCA 然后倍增统计答案

---

思路

以下设 f 为 u 和 v 的最近公共祖先

1. 以结点 1 为根，套路性 dfs，并求出倍增祖先数组 fa[][] & 结点深度 dep[] & 根到每个结点的边权和 wn[]
   • $O(n \log n)$
2. 对于每个 DIST u v 操作，答案显然为 wn[u] + wn[v] - 2 * wn[f]
   • 单次 $O( \log n)$
3. 对于每个 KTH u v k 操作，分情况讨论。
   • 若 dep[u] - dep[f] + 1 < k，答案即为 u 的 k 级祖先；
   • 若 dep[u] - dep[f] + 1 > k，答案为 v 的 祖先，且为 dep[u] + dep[v] - 2 * dep[k] + 2 - k 级祖先。考虑 u 到 v 的路径上共有 dep[u] + dep[v] - 2 * dep[f] + 1 个结点，得到这个式子；
   • 若 dep[u] - dep[f] + 1 == k， 答案为 f。可特判，也可并入前两种情况处理。
   • 单次 $ O( \log n) $

总复杂度 $ O((n + q) \log n) $

---

变量解释与代码

cin: 重载的快读

MX: $ \lfloor \log_2 N \rfloor $

queryt(u, v, k): 返回 KTH u v k 操作的答案

其余变量意义同 思路 部分

代码 (c++11) :

#include<algorithm>
#include<cstdio>
#include<cstring>

struct IO {
  template<typename T>
  inline IO operator>>(T &n) {
    n=0; char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') n=(n<<3)+(n<<1)+(c^48),c=getchar();
    return *this; // n >= 0
  }
} cin;
// 不要 iostream + using namespace std！会 CE 的！

constexpr int MX = 14;

char op[5];
int T, N, u, v, w, tot, head[10003], dep[10003], wn[10003], fa[10003][15];

struct Edge {
  int nxt, to, w;
} e[20003];

inline void addEdge(int u, int v, int w) {
  e[++tot] = {head[u], v, w};
  head[u] = tot;
}

void dfs(int u, int f) {
  // 预处理
  dep[u] = dep[f] + 1;
  fa[u][0] = f;
  for (int i = 1; (1 << i) <= dep[u]; ++i)
    fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (int i = head[u], v; i; i = e[i].nxt) {
    if ((v = e[i].to) == f) continue;
    wn[v] = wn[u] + e[i].w;
    dfs(v, u);
  }
}

int Lca(int u, int v) {
  // 倍增求 LCA
  if (dep[u] < dep[v]) std::swap(u, v);
  for (int i = MX; i >= 0; --i)
    if (dep[v] <= dep[u] - (1 << i))
      u = fa[u][i];
  if (u == v) return u;
  for (int i = MX; i >= 0; --i)
    if (fa[u][i] != fa[v][i])
      u = fa[u][i], v = fa[v][i];
  return fa[u][0];
}

int queryt(int u, int v, int k) {
  // 分类讨论
  int f = Lca(u, v);
  if (dep[u] - dep[f] + 1 <= k) {
    // 若答案为 $v 的祖先，则转换为求 u 的祖先的情况，简化代码
    k = dep[u] + dep[v] - (dep[f] << 1) + 2 - k;
    u = v;
  }
  for (int i = MX; i >= 0; --i)
    // 倍增维护答案
    if (k >= (1 << i) + 1) {
      u = fa[u][i];
      k -= (1 << i);
    }
  return u;
}

void init() {
  // 多测不清空，爆零两行泪
  tot = wn[1] = 0;
  memset(fa, 0, sizeof fa);
  memset(head, 0, sizeof head);
  cin >> N;
  for (int i = 1; i < N; ++i) {
    cin >> u >> v >> w;
    addEdge(u, v, w);
    addEdge(v, u, w);
  }
}

int main() {
  for (cin >> T; T; --T) {
    init();
    dfs(1, 0);
    while(1) {
      scanf("%s", op);
      if (op[1] == 'O') break;
      if (op[1] == 'I') {
        cin >> u >> v;
        printf("%d\n", wn[u] + wn[v] - (wn[Lca(u, v)] << 1));
      } else {
        cin >> u >> v >> w;
        printf("%d\n", queryt(u, v, w));
      }
    }
  }
  return 0;
}