洛谷 P3128 [USACO15DEC] Max Flow P

// P3128 [USACO15DEC] Max Flow P —— 正解：倍增求 LCA ＋ **树上差分**，最后一趟子树求和
//
// ★★★ 这是 LCA 最常见的**第二个**用法（第一个是「问两点的 LCA / 距离」）：
//   K 条路径，每条把沿途所有点 +1，最后问哪个点最大。
//   一条一条走是 O(K × 深度)，顶格 10⁵ × 5×10⁴ = **50 亿**；
//   而树上差分把「一条路径 +1」压成**四次单点加**：
//
//       d[s]++,  d[t]++,  d[lca]--,  d[fa[lca]]--
//
//   最后自底向上把子树和累起来，每个点的值就是它被盖了多少次。⇒ O((N + K) log N)。
//
// ★ 为什么是「减两次」而不是「减一次」：`d[s]` 和 `d[t]` 各把**根到自己**那一路都 +1 了，
//   于是根到 `lca` 那一段被加了两遍 —— `lca` 自己要**留一份**（它在路径上），
//   所以在 `lca` 减一次、在 `lca` 的**父亲**再减一次，把上面那一整段彻底抹平。
//
// ⚠⚠ 而 `fa[root]` 这一处正是[第 52 章](/ch/52-tree-diff/)那条
//   「**上一章的正确写法就是这一章的 bug**」的现场：
//   [P3379](/sol/p3379/) 的正解写的是 `up[0][root] = root`（根的父亲是它自己，跳过头就停在根），
//   照抄到这儿，`lca` 恰好是根时 `d[fa[lca]]--` 就变成**又减了一次 `d[root]`**。
//   ⇒ 这里必须让根的父亲是 **0 号点**（一个不存在的点，专门收这笔账）。

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

const int MAXN = 50005;
const int LOG = 17;                       // 2^16 = 65536 > 5×10⁴

int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], ecnt;
int up[MAXN][LOG], dep[MAXN], order_[MAXN], d[MAXN];
int n, k;

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

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int j = 0; j < LOG; j++) if ((diff >> j) & 1) u = up[u][j];
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; j--) if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; }
    return up[u][0];
}

int main() {
    if (scanf("%d %d", &n, &k) != 2) return 0;
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        addEdge(x, y); addEdge(y, x);     // ⚠ 无向边，两边都要存
    }

    /* BFS 求 dep 和 up[·][0]（⚠ 别用递归，顶格链有 5 万层）*/
    {
        vector<char> vis(n + 1, 0);
        int cnt = 0;
        order_[cnt++] = 1; vis[1] = 1; dep[1] = 1;
        up[1][0] = 0;                     // ⚠⚠ 根的父亲是 0 号点，不是它自己
        for (int i = 0; i < cnt; i++) {
            int u = order_[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[v][0] = u; order_[cnt++] = v;
            }
        }
    }
    for (int j = 1; j < LOG; j++)
        for (int v = 1; v <= n; v++)
            up[v][j] = up[up[v][j - 1]][j - 1];

    for (int i = 0; i < k; i++) {
        int s, t;
        if (scanf("%d %d", &s, &t) != 2) return 0;
        int l = lca(s, t);
        d[s]++; d[t]++; d[l]--;
        if (up[l][0]) d[up[l][0]]--;      // ★ l 是根时 up[l][0] == 0，这笔账没人要收
    }

    /* 自底向上把子树和累起来 —— ⚠ 必须**逆着** BFS 序走 */
    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        int u = order_[i];
        ans = max(ans, d[u]);
        if (up[u][0]) d[up[u][0]] += d[u];
    }
    printf("%d\n", ans);
    return 0;
}

// P3128 的两笔账：这份数据长什么样，以及两条路各做多少次基本动作（机器无关）
//
// 用法：./p3128Count <csv|table> < 一份输入
//
// ★ 顺手数两个决定成败的东西：
//   ① **有几个询问的 LCA 就是根** —— 那是错法③的触发条件，而它的补集是错法①的；
//   ② **最大值是不是落在根上** —— 错法③还要过这一关才会被看见。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;
const int LOG = 17;
static int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], ecnt;
static int up[MAXN][LOG], dep[MAXN], order_[MAXN], d[MAXN];
static int n, k;

static int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int j = 0; j < LOG; j++) if ((diff >> j) & 1) u = up[u][j];
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; j--) if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; }
    return up[u][0];
}

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";
    if (scanf("%d %d", &n, &k) != 2) return 0;
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        to_[++ecnt] = y; nxt_[ecnt] = head_[x]; head_[x] = ecnt;
        to_[++ecnt] = x; nxt_[ecnt] = head_[y]; head_[y] = ecnt;
    }
    {
        vector<char> vis(n + 1, 0);
        int c = 0;
        order_[c++] = 1; vis[1] = 1; dep[1] = 1; up[1][0] = 0;
        for (int i = 0; i < c; i++) {
            int u = order_[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[v][0] = u; order_[c++] = v;
            }
        }
    }
    for (int j = 1; j < LOG; j++) for (int v = 1; v <= n; v++) up[v][j] = up[up[v][j - 1]][j - 1];

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

    long long bruteSteps = 0, lcaRoot = 0;
    for (int i = 0; i < k; i++) {
        int s, t;
        if (scanf("%d %d", &s, &t) != 2) return 0;
        int l = lca(s, t);
        if (l == 1) lcaRoot++;
        bruteSteps += (long long)(dep[s] - dep[l]) + (dep[t] - dep[l]) + 1;   // 路径上有几个点
        d[s]++; d[t]++; d[l]--;
        if (up[l][0]) d[up[l][0]]--;
    }
    /* 自底向上把子树和累起来 —— 累完之后 d[u] 就是「u 被盖了多少次」 */
    for (int i = n - 1; i >= 1; i--) {
        int u = order_[i];
        d[up[u][0]] += d[u];
    }
    int ans = 0, ties = 0, argmaxRoot = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, d[i]);
    for (int i = 1; i <= n; i++) if (d[i] == ans) ties++;
    argmaxRoot = (d[1] == ans);

    /* 倍增那条路的基本动作：建表 n·(LOG−1) 次写 ＋ 每个询问最多 2·LOG 次读 */
    long long fastSteps = (long long)n * (LOG - 1) + (long long)k * 2 * LOG;

    vector<pair<string, string> > out;
    out.push_back(make_pair("n", to_string(n)));
    out.push_back(make_pair("k", to_string(k)));
    out.push_back(make_pair("maxdep", to_string(maxDep)));
    out.push_back(make_pair("ans", to_string(ans)));
    out.push_back(make_pair("lca_root", to_string(lcaRoot)));
    out.push_back(make_pair("argmax_root", to_string(argmaxRoot)));
    out.push_back(make_pair("ties", to_string(ties)));
    out.push_back(make_pair("brute_steps", to_string(bruteSteps)));
    out.push_back(make_pair("fast_steps", to_string(fastSteps)));
    out.push_back(make_pair("ratio", to_string(bruteSteps / fastSteps)));
    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;
}