洛谷 P3379 【模板】最近公共祖先（LCA）

// P3379【模板】最近公共祖先（LCA）—— 正解：倍增，预处理 O(n log n)、单次查询 O(log n)
//
// ★ 骨架就是[第 51 章](/ch/51-lca/)第 7 步那份 `fast.cpp`，一个字都没改（那道题就是照这道题写的）。
//   这一页要做的是把**真题题面上那几行数字**一行一行乘一遍，而乘完之后有三处和正文不一样：
//
//   ① ⚠⚠ **暴力过不去了** —— 正文第 3 步量的是「随机树上暴力一点都不慢」，
//      而这道题的题面末尾写着：**「2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。」**
//      ⇒ 那句「不慢」的主语是**随机树**，而出题人专门补了链。
//   ② ⚠ **建表必须 BFS**：`n` 到 5×10⁵，一条链递归下去必爆栈（正文第 9 步）。
//   ③ ⚠⚠ **真正吃掉时限的不是读入，是那张 40 MB 的表怎么摆** ——
//      `n + m` 到 10⁶ 行、约 2×10⁶ 个整数，看着像一道读入题，
//      可快读实测只要 **20 毫秒**（时限 2 秒的 1%）；
//      而 `up[LOG][MAXN]` 这个下标顺序在顶格星形树上光查询就要 **1162 毫秒**
//      —— 把两个下标换个顺序（`p3379T.cpp`）是 **113 毫秒**。解析页第 ⑤ 步量了这件事。
//
// ⚠ 而题面自己点名了一处：**「不保证 a ≠ b」** —— 那正是正文 `wrongNoSame.cpp` 那个坑。

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

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

int up[LOG][MAXN];
int dep[MAXN];
int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], ecnt;
int n, m, root;

inline void addEdge(int u, int v) { to_[++ecnt] = v; nxt_[ecnt] = head_[u]; head_[u] = ecnt; }

/* ---- 快读：2×10⁶ 个整数，这道题上它是分数线的一部分 ---- */
static char ibuf[1 << 22];
static size_t ilen = 0, ipos = 0;
inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return -1; }
    return ibuf[ipos++];
}
inline int readInt() {
    int c = gc(), x = 0;
    while (c < '0' || c > '9') c = gc();
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}

/** BFS 一趟求出 dep 和 up[0]，再把 up 的其余层推出来 */
void build() {
    vector<char> vis(n + 1, 0);
    vector<int> que;
    que.reserve(n);
    dep[root] = 0;
    up[0][root] = root;                   // ⚠ 根的父亲是它自己
    vis[root] = 1;
    que.push_back(root);
    for (size_t i = 0; i < que.size(); i++) {
        int u = que[i];
        for (int e = head_[u]; e; e = nxt_[e]) {
            int v = to_[e];
            if (vis[v]) continue;
            vis[v] = 1;
            dep[v] = dep[u] + 1;
            up[0][v] = u;
            que.push_back(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;                 // ⚠ 一个是另一个的祖先（题面明说「不保证 a ≠ b」）
    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 正下方，再上一步才是答案
}

/* ---- 快写 ---- */
static char obuf[1 << 22];
static size_t opos = 0;
inline void writeInt(int x) {
    if (opos + 16 > sizeof(obuf)) { fwrite(obuf, 1, opos, stdout); opos = 0; }
    char t[12];
    int k = 0;
    if (!x) t[k++] = '0';
    while (x) { t[k++] = (char)('0' + x % 10); x /= 10; }
    while (k) obuf[opos++] = t[--k];
    obuf[opos++] = '\n';
}

int main() {
    n = readInt(); m = readInt(); root = readInt();
    for (int i = 0; i < n - 1; i++) {
        int u = readInt(), v = readInt();
        addEdge(u, v);
        addEdge(v, u);
    }
    build();
    for (int i = 0; i < m; i++) {
        int u = readInt(), v = readInt();
        writeInt(lca(u, v));
    }
    fwrite(obuf, 1, opos, stdout);
    return 0;
}

// P3379 的三笔账：读入 / 建表 / 查询各花多少，以及**那张表被读了多少次**（机器无关）
//
// 用法：./p3379Count <csv|table> < 一份输入
//
// ★ 它把同一份数据喂给**两种存法**：
//     A = up[LOG][MAXN]（正文那份，固定 k 时 v 连续）
//     B = up[MAXN][LOG]（转置，固定 v 时 k 连续）
//   两版的**每一步都一模一样**，连「读了多少次 up」都一个不差 ——
//   ⇒ 于是这一份能把[两把尺子打架](/sol/p1074/)量得干干净净：
//     **次数完全相同，秒表差好几倍，而差的是「那些活离得多远」。**

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

static double nowMs() { struct timeval tv; gettimeofday(&tv, nullptr); return tv.tv_sec * 1000.0 + tv.tv_usec / 1000.0; }

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

static int upA[LOG][MAXN];
static int upB[MAXN][LOG];
static int dep[MAXN];
static int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], ecnt;
static int n, m, root;
static long long reads;                      // 读了多少次 up[][]

static char ibuf[1 << 22];
static size_t ilen = 0, ipos = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return -1; }
    return ibuf[ipos++];
}
static inline int readInt() {
    int c = gc(), x = 0;
    while (c < '0' || c > '9') c = gc();
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}

static void bfs() {
    vector<char> vis(n + 1, 0);
    vector<int> que;
    que.reserve(n);
    dep[root] = 0; upA[0][root] = root; vis[root] = 1; que.push_back(root);
    for (size_t i = 0; i < que.size(); i++) {
        int u = que[i];
        for (int e = head_[u]; e; e = nxt_[e]) {
            int v = to_[e];
            if (vis[v]) continue;
            vis[v] = 1; dep[v] = dep[u] + 1; upA[0][v] = u; que.push_back(v);
        }
    }
}

template <bool COUNT>
static int lcaA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++) { if (COUNT) reads++; if ((d >> k) & 1) u = upA[k][u]; }
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--) { if (COUNT) reads += 2; if (upA[k][u] != upA[k][v]) { u = upA[k][u]; v = upA[k][v]; } }
    return upA[0][u];
}

static int lcaB(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++) if ((d >> k) & 1) u = upB[u][k];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--) if (upB[u][k] != upB[v][k]) { u = upB[u][k]; v = upB[v][k]; }
    return upB[u][0];
}

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";

    double t0 = nowMs();
    n = readInt(); m = readInt(); root = readInt();
    for (int i = 0; i < n - 1; i++) {
        int u = readInt(), v = readInt();
        to_[++ecnt] = v; nxt_[ecnt] = head_[u]; head_[u] = ecnt;
        to_[++ecnt] = u; nxt_[ecnt] = head_[v]; head_[v] = ecnt;
    }
    vector<pair<int, int> > qs(m);
    for (int i = 0; i < m; i++) { qs[i].first = readInt(); qs[i].second = readInt(); }
    double tRead = nowMs() - t0;

    bfs();
    int maxDep = 0;
    for (int i = 1; i <= n; i++) maxDep = max(maxDep, dep[i]);

    /* 建表：两种存法各一次 */
    double t1 = nowMs();
    for (int k = 1; k < LOG; k++) for (int v = 1; v <= n; v++) upA[k][v] = upA[k - 1][upA[k - 1][v]];
    double buildA = nowMs() - t1;
    for (int v = 1; v <= n; v++) upB[v][0] = upA[0][v];
    double t2 = nowMs();
    for (int k = 1; k < LOG; k++) for (int v = 1; v <= n; v++) upB[v][k] = upB[upB[v][k - 1]][k - 1];
    double buildB = nowMs() - t2;

    /* 查询：两种存法各一次；顺手把「读了多少次 up」数出来（两版必然相同） */
    long long sumA = 0, sumB = 0;
    double t3 = nowMs();
    for (int i = 0; i < m; i++) sumA += lcaA<false>(qs[i].first, qs[i].second);
    double queryA = nowMs() - t3;
    double t4 = nowMs();
    for (int i = 0; i < m; i++) sumB += lcaB(qs[i].first, qs[i].second);
    double queryB = nowMs() - t4;
    reads = 0;
    for (int i = 0; i < m; i++) lcaA<true>(qs[i].first, qs[i].second);

    /* 暴力「一步一步爬」要走多少步 —— 机器无关
       ★ 不用真去爬：那个循环走的步数**恰好等于 u 到 v 的距离**
       （对齐阶段走 |dep u − dep v| 步，一起走那段两人各走 min − dep[lca] 步，加起来正好是 dist）。
       ⇒ 于是顶格的链上也能一秒钟数完，而真去爬要 2.5×10¹¹ 步。 */
    long long climb = 0;
    for (int i = 0; i < m; i++) {
        int u = qs[i].first, v = qs[i].second;
        int l = lcaB(u, v);
        climb += (long long)(dep[u] - dep[l]) + (dep[v] - dep[l]);
    }

    char buf[64];
    vector<pair<string, string> > out;
    auto put = [&](const string& k, double x, int prec = 1) {
        snprintf(buf, sizeof(buf), "%.*f", prec, x); out.push_back(make_pair(k, string(buf)));
    };
    out.push_back(make_pair("n", to_string(n)));
    out.push_back(make_pair("m", to_string(m)));
    out.push_back(make_pair("maxdep", to_string(maxDep)));
    out.push_back(make_pair("same", string(sumA == sumB ? "1" : "0")));
    out.push_back(make_pair("reads", to_string(reads)));
    out.push_back(make_pair("climb", to_string(climb)));
    put("ms_read", tRead);
    put("ms_buildA", buildA);
    put("ms_buildB", buildB);
    put("ms_queryA", queryA);
    put("ms_queryB", queryB);
    put("ratio_query", queryB > 0 ? queryA / queryB : 0, 2);

    if (mode == "csv") for (size_t i = 0; i < out.size(); i++) printf("%s,%s\n", out[i].first.c_str(), out[i].second.c_str());
    else for (size_t i = 0; i < out.size(); i++) printf("  %-12s %s\n", out[i].first.c_str(), out[i].second.c_str());
    return 0;
}