LCA 与倍增：把「往上跳多少步」拆成二进制

// 标准答案：一步一步往上爬 —— 而且用的是和正解**完全不同**的两条路
//
// ★ 这一份故意不建 dep 数组、也不套那个距离公式，两问各自独立算出来：
//   · **LCA**：把 u 到根的整条链**做个记号**，再让 v 一步步往上走 ——
//     第一个撞上记号的点就是 LCA。（这一步一个「深度」都没用到。）
//   · **距离**：就是「u 爬到 LCA 用了几步」＋「v 爬到 LCA 用了几步」，**数出来的**，
//     不是 dep[u] + dep[v] − 2·dep[lca] 算出来的。
//   ⇒ 于是它能验正解那两件事里的任何一件（第 34 章那条：先找一个能独立算出来的量）。
//
// 复杂度是 O(深度) 一次询问。⚠ 而这一章第 4 步会量出一件很反直觉的事：
//   **随机树的深度只有 log 级**，所以在顺手写的数据上，这份暴力一点都不慢。
//
// ⚠ 记号用「时间戳」而不是每次清空 —— 清空是 O(n)，会把「深度」这个主语盖掉。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
int fa[MAXN];
int stamp_[MAXN];
vector<int> g[MAXN];
int n, q, root;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q >> root;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    /* BFS 一趟只求父亲（不求深度 —— 下面用不上） */
    {
        vector<char> vis(n + 1, 0);
        queue<int> que;
        fa[root] = root;
        vis[root] = 1;
        que.push(root);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int v : g[u]) {
                if (vis[v]) continue;
                vis[v] = 1;
                fa[v] = u;
                que.push(v);
            }
        }
    }

    for (int i = 1; i <= q; i++) {
        int u, v;
        cin >> u >> v;
        int a = u, stepU = 0;
        while (true) {                    // ① 把 u 到根的链做上记号
            stamp_[a] = i;
            if (a == root) break;
            a = fa[a];
        }
        int b = v, stepV = 0;
        while (stamp_[b] != i) { b = fa[b]; stepV++; }   // ② v 往上走，第一个撞上记号的就是 LCA
        int lca = b;
        a = u;
        while (a != lca) { a = fa[a]; stepU++; }         // ③ 距离：两段各数几步
        cout << lca << ' ' << stepU + stepV << '\n';
    }
    return 0;
}

// 换一把尺子：数「往上爬了多少步」
//
// ★ 为什么需要它：这一章的秒表在小数据上全是 0.00 秒，而**步数**是能数出来的、
//   换台机器也不变的东西。两种做法各放一个计数器，数的是同一个动作：
//       **顺着父亲指针往上走一格。**
//   （倍增那边一次「跳 2^k 步」也只算**一格** —— 它本来就是一次数组访问。）
//
// 顺带把树本身量一下：最大深度、平均深度。⚠ 这两个数才是这一章真正的主角 ——
//   第 4 步会看到：**随机树的深度只有 log 级**，所以暴力在顺手写的数据上一点都不慢。
//
// 用法：./count < 输入        （和主程序同一份输入）
//       ./count csv < 输入    只打 `键,值`，给 check:viz 用

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
const int LOG = 20;

int up[LOG][MAXN];
int dep[MAXN], fa[MAXN], stamp_[MAXN];
vector<int> g[MAXN];
int n, q, root;

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    cin >> n >> q >> root;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    {
        vector<char> vis(n + 1, 0);
        queue<int> que;
        fa[root] = root;
        vis[root] = 1;
        que.push(root);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int v : g[u]) if (!vis[v]) { vis[v] = 1; dep[v] = dep[u] + 1; fa[v] = u; que.push(v); }
        }
    }
    for (int v = 1; v <= n; v++) up[0][v] = fa[v];
    for (int k = 1; k < LOG; k++) for (int v = 1; v <= n; v++) up[k][v] = up[k - 1][up[k - 1][v]];

    int maxDep = 0;
    double avgDep = 0;
    for (int v = 1; v <= n; v++) { maxDep = max(maxDep, dep[v]); avgDep += dep[v]; }
    avgDep /= n;

    long long stepBrute = 0, stepFast = 0, rootLca = 0, ancPair = 0;
    for (int i = 1; i <= q; i++) {
        int u, v;
        cin >> u >> v;
        /* ① 暴力：标记 u 的祖先链，再让 v 往上撞 */
        {
            int a = u;
            while (true) { stamp_[a] = i; stepBrute++; if (a == root) break; a = fa[a]; }
            int b = v;
            while (stamp_[b] != i) { b = fa[b]; stepBrute++; }
            int lca = b;
            a = u;
            while (a != lca) { a = fa[a]; stepBrute++; }
        }
        /* ② 倍增 */
        {
            int a = u, b = v;
            if (dep[a] < dep[b]) swap(a, b);
            int d = dep[a] - dep[b];
            for (int k = 0; k < LOG; k++) if ((d >> k) & 1) { a = up[k][a]; stepFast++; }
            if (a == b) { ancPair++; if (a == root) rootLca++; continue; }
            for (int k = LOG - 1; k >= 0; k--)
                if (up[k][a] != up[k][b]) { a = up[k][a]; b = up[k][b]; stepFast += 2; }
            if (up[0][a] == root) rootLca++;
        }
    }

    if (csv) {
        printf("n,%d\nq,%d\nmaxdep,%d\navgdep,%.2f\nbrute,%lld\nfast,%lld\nrootlca,%lld\nancpair,%lld\n",
               n, q, maxDep, avgDep, stepBrute, stepFast, rootLca, ancPair);
        return 0;
    }
    printf("%d 个点、%d 个询问，根是 %d\n\n", n, q, root);
    printf("  树的最大深度        %10d\n", maxDep);
    printf("  树的平均深度        %13.2f\n", avgDep);
    printf("\n  暴力  一共往上爬了 %12lld 步   （平均每次 %.2f 步）\n", stepBrute, (double)stepBrute / q);
    printf("  倍增  一共跳了     %12lld 次   （平均每次 %.2f 次）\n", stepFast, (double)stepFast / q);
    printf("\n  ★ 暴力 / 倍增 = %.1f 倍\n", stepFast ? (double)stepBrute / stepFast : 0.0);
    printf("  ⚠ LCA 恰好就是根的询问占 %.1f%%；一个点是另一个点祖先的占 %.1f%%\n",
           100.0 * rootLca / q, 100.0 * ancPair / q);
    return 0;
}

// 正解：倍增求 LCA，预处理 O(n log n)、单次查询 O(log n)
//
// ★ 关键的一步只有一句话：**把「往上跳多少步」看成二进制**。
//   这和第 42 章快速幂是同一件事换了个主语 —— 那里拆的是指数，这里拆的是步数。
//
//       up[0][v] = fa[v]
//       up[k][v] = up[k-1][ up[k-1][v] ]      // 跳 2^k 步 = 连着跳两次 2^(k-1) 步
//
//   有了这张表，查询就是两段**完全不同**的循环（这两段最容易糊在一起，正文第 6 步专门拆开讲）：
//     ① 对齐深度：把 dep[u] − dep[v] 拆成二进制，该跳哪几位就跳哪几位（k 从小到大、从大到小都行）；
//     ② 一起往上跳：k 从大到小，★ 只在 up[k][u] != up[k][v] 时才跳 ——
//        跳完两个人停在 LCA 的**正下方**，答案是 up[0][u]。
//   ⚠ 而 ① 和 ② 之间必须先判一次 u == v（那时 u 就是 LCA，进 ② 会跳过头）。
//
// ⚠⚠ 建表这一趟**一定要用 BFS，不能递归 DFS**：
//   这道题的最坏形状就是一条链，而第 30 章实测过 —— 本机 8 MB 栈、一帧约 30 字节，
//   递归到 28 万层就段错误。50 万个点的链必炸。
//
// ⚠ 根的父亲设成**它自己**：这样「跳过头」会老老实实停在根上，不用到处判边界。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
const int LOG = 20;                       // 2^19 = 524288 > 5×10^5，取 20 留一格

int up[LOG][MAXN];
int dep[MAXN];
vector<int> g[MAXN];
int n, q, root;

/** BFS 一趟求出 dep 和 up[0]，再把 up 的其余层推出来 */
void build() {
    vector<char> vis(n + 1, 0);
    queue<int> que;
    dep[root] = 0;
    up[0][root] = root;                   // ⚠ 根的父亲是它自己
    vis[root] = 1;
    que.push(root);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int v : g[u]) {
            if (vis[v]) continue;
            vis[v] = 1;
            dep[v] = dep[u] + 1;
            up[0][v] = u;
            que.push(v);
        }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);      // ⚠ 先保证 u 是更深的那个
    int d = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)         // ① 对齐深度：把 d 拆成二进制
        if ((d >> k) & 1) u = up[k][u];
    if (u == v) return u;                 // ⚠ 一个是另一个的祖先，到此为止
    for (int k = LOG - 1; k >= 0; k--)    // ② 一起往上跳：只在「还不一样」时跳
        if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
    return up[0][u];                      // ⚠ 停在 LCA 正下方，再上一步才是答案
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q >> root;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    build();
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        int a = lca(u, v);
        cout << a << ' ' << dep[u] + dep[v] - 2 * dep[a] << '\n';
    }
    return 0;
}

// ⚠ 把「建表那趟不能用递归 DFS」演示出来
//
// 这一章的最坏形状是**一条链**，而链正好也是递归最怕的东西：
// 递归求 dep / fa 时，链有多长就要压多少层栈。
// 第 30 章实测过：本机默认栈 8 MB、一帧约 30 字节，压到二十几万层就段错误。
//
// 用法：./deep dfs  < 输入    用**递归** DFS 建表，打印它压了多少层（链上会直接段错误）
//       ./deep bfs  < 输入    用 BFS 建表，打印同一棵树的最大深度（永远不会炸）
//       ./deep csv  < 输入    只打 `键,值`（走 BFS 那条路，安全），给 check:viz 用
//
// ⚠ 两条路算出来的 dep 数组是**一模一样**的 —— 差别只在「谁来记住还没做完的事」：
//   递归让操作系统的栈记，BFS 让你自己的队列记（队列在堆上，堆比栈大得多）。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
int dep[MAXN], fa[MAXN];
vector<int> g[MAXN];
int n, q, root;
int curDepth = 0, maxStack = 0;

/** 递归版：⚠ 链上会压到 n 层 */
void dfs(int u, int p) {
    curDepth++;
    maxStack = max(maxStack, curDepth);
    fa[u] = p;
    dep[u] = (u == root) ? 0 : dep[p] + 1;
    for (int v : g[u]) if (v != p) dfs(v, u);
    curDepth--;
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string mode = (argc > 1) ? argv[1] : "bfs";
    cin >> n >> q >> root;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    if (mode == "dfs") {
        printf("用递归 DFS 建表（n = %d）…\n", n);
        fflush(stdout);
        dfs(root, root);
        printf("没炸。最深压了 %d 层栈。\n", maxStack);
        return 0;
    }

    vector<char> vis(n + 1, 0);
    queue<int> que;
    fa[root] = root;
    vis[root] = 1;
    que.push(root);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int v : g[u]) if (!vis[v]) { vis[v] = 1; dep[v] = dep[u] + 1; fa[v] = u; que.push(v); }
    }
    int mx = 0;
    for (int v = 1; v <= n; v++) mx = max(mx, dep[v]);
    if (mode == "csv") { printf("n,%d\nmaxdep,%d\n", n, mx); return 0; }
    printf("用 BFS 建表（n = %d）：最大深度 %d，一层栈都没压。\n", n, mx);
    printf("⚠ 同一棵树用递归 DFS 建表，要压的栈层数就是这个最大深度 + 1 = %d。\n", mx + 1);
    return 0;
}

// 正解：倍增求 LCA，预处理 O(n log n)、单次查询 O(log n)
//
// ★ 关键的一步只有一句话：**把「往上跳多少步」看成二进制**。
//   这和第 42 章快速幂是同一件事换了个主语 —— 那里拆的是指数，这里拆的是步数。
//
//       up[0][v] = fa[v]
//       up[k][v] = up[k-1][ up[k-1][v] ]      // 跳 2^k 步 = 连着跳两次 2^(k-1) 步
//
//   有了这张表，查询就是两段**完全不同**的循环（这两段最容易糊在一起，正文第 6 步专门拆开讲）：
//     ① 对齐深度：把 dep[u] − dep[v] 拆成二进制，该跳哪几位就跳哪几位（k 从小到大、从大到小都行）；
//     ② 一起往上跳：k 从大到小，★ 只在 up[k][u] != up[k][v] 时才跳 ——
//        跳完两个人停在 LCA 的**正下方**，答案是 up[0][u]。
//   ⚠ 而 ① 和 ② 之间必须先判一次 u == v（那时 u 就是 LCA，进 ② 会跳过头）。
//
// ⚠⚠ 建表这一趟**一定要用 BFS，不能递归 DFS**：
//   这道题的最坏形状就是一条链，而第 30 章实测过 —— 本机 8 MB 栈、一帧约 30 字节，
//   递归到 28 万层就段错误。50 万个点的链必炸。
//
// ⚠ 根的父亲设成**它自己**：这样「跳过头」会老老实实停在根上，不用到处判边界。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
const int LOG = 20;                       // 2^19 = 524288 > 5×10^5，取 20 留一格

int up[LOG][MAXN];
int dep[MAXN];
vector<int> g[MAXN];
int n, q, root;

/** BFS 一趟求出 dep 和 up[0]，再把 up 的其余层推出来 */
void build() {
    vector<char> vis(n + 1, 0);
    queue<int> que;
    dep[root] = 0;
    up[0][root] = root;                   // ⚠ 根的父亲是它自己
    vis[root] = 1;
    que.push(root);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int v : g[u]) {
            if (vis[v]) continue;
            vis[v] = 1;
            dep[v] = dep[u] + 1;
            up[0][v] = u;
            que.push(v);
        }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);      // ⚠ 先保证 u 是更深的那个
    int d = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)         // ① 对齐深度：把 d 拆成二进制
        if ((d >> k) & 1) u = up[k][u];
    if (u == v) return u;                 // ⚠ 一个是另一个的祖先，到此为止
    for (int k = LOG - 1; k >= 0; k--)    // ② 一起往上跳：只在「还不一样」时跳
        if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
    return up[0][u];                      // ⚠ 停在 LCA 正下方，再上一步才是答案
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q >> root;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    build();
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        int a = lca(u, v);
        cout << a << ' ' << dep[u] + dep[v] - 2 * dep[a] << '\n';
    }
    return 0;
}

// ★★ 倍增不只是 LCA：同一张表，换个东西记
//
// 题面（章末那道小题）：树的每条边带一个权 w。q 个询问，每次给 u v k，输出两个数：
//   ① u 往上数第 k 个祖先是谁（不存在输出 0）；
//   ② u 到 v 的路径上，最大的那条边权是多少（u == v 时没有边，输出 0）。
//
// ★ 这两问和 LCA 用的是**同一张 up 表**，只是多记了一个东西：
//       mx[k][v] = 从 v 往上跳 2^k 步，这一段路上最大的边权
//       mx[k][v] = max( mx[k-1][v], mx[k-1][ up[k-1][v] ] )      // 和 up 一模一样的递推
//
// ⇒ ① 第 k 个祖先：把 k 拆成二进制，该跳哪几位跳哪几位 —— 这就是「对齐深度」那一段单独拿出来；
//    ② 路径最大边权：把 LCA 的两段循环原样跑一遍，沿途 max 一下就行。
//
// ★ 这一节想说明的只有一句话：**倍增是一类技术，不是一道模板题。**
//   凡是「沿着一条链往上走、而且能合并」的东西（最大值、最小值、和、gcd…）都能这么记。
// ⚠ 但「能合并」是有条件的：这里的 max 可交换可结合，换成「路径上第二大」就不行了。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int LOG = 18;

int up[LOG][MAXN], mx[LOG][MAXN];
int dep[MAXN];
vector<pair<int, int>> g[MAXN];
int n, q, root;

void build() {
    vector<char> vis(n + 1, 0);
    queue<int> que;
    dep[root] = 0;
    up[0][root] = root;
    mx[0][root] = 0;
    vis[root] = 1;
    que.push(root);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i].first, w = g[u][i].second;
            if (vis[v]) continue;
            vis[v] = 1;
            dep[v] = dep[u] + 1;
            up[0][v] = u;
            mx[0][v] = w;
            que.push(v);
        }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++) {
            up[k][v] = up[k - 1][up[k - 1][v]];
            mx[k][v] = max(mx[k - 1][v], mx[k - 1][up[k - 1][v]]);   // ★ 和 up 同一个递推
        }
}

/** u 往上第 k 个祖先，没有就返回 0 */
int kth(int u, int k) {
    if (k > dep[u]) return 0;                       // ⚠ 跳出树外了
    for (int b = 0; b < LOG; b++)
        if ((k >> b) & 1) u = up[b][u];
    return u;
}

/** u 到 v 路径上的最大边权 */
int pathMax(int u, int v) {
    int res = 0;
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)                   // ① 对齐深度，顺手 max
        if ((d >> k) & 1) { res = max(res, mx[k][u]); u = up[k][u]; }
    if (u == v) return res;
    for (int k = LOG - 1; k >= 0; k--)              // ② 一起往上跳，顺手 max
        if (up[k][u] != up[k][v]) {
            res = max(res, max(mx[k][u], mx[k][v]));
            u = up[k][u];
            v = up[k][v];
        }
    return max(res, max(mx[0][u], mx[0][v]));       // ⚠ 最后那一步（到 LCA）也算
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q >> root;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }
    build();
    for (int i = 0; i < q; i++) {
        int u, v, k;
        cin >> u >> v >> k;
        cout << kth(u, k) << ' ' << pathMax(u, v) << '\n';
    }
    return 0;
}