洛谷 P4551 最长异或路径

// P4551 最长异或路径 —— 正解：把「树上路径」变成「一个数」，再上 01-Trie。
//
// ★★ 这道题挂在第 49 章的题单里，可它**一个字符串哈希都用不上** ——
//   题单注解自己写着：「它其实是第 50 章 01-Trie 的题。放在这儿是想说明
//   『把东西变成一个数』之后，路还能往哪儿走。」
//   ⇒ 这一章教的是那**半步**：把一个复杂的东西压成一个整数，让「比较」变成 O(1)。
//     这道题把同一半步用在**树上的路径**上。
//
// ★★★ 那半步只有一句话，而且证明只有一行：
//     令 d[u] = 根到 u 的所有边权的异或。
//     则 u 到 v 的路径异或 = d[u] ^ d[v]。
//   为什么：路径 = (根→u) ⊕ (根→v)，两条里**根到 LCA 那一段被走了两遍**，
//   而 `x ^ x = 0` ⇒ 它自己抵消了。
//   ⚠⚠ 注意这和[第 52 章树上差分](/ch/52-tree-diff/)那套**求和**的公式**不一样**：
//     求和是 `s[u] + s[v] − 2·s[lca]`（要减两遍），异或是**一遍都不用减**。
//     照搬那个公式、写成 `d[u] ^ d[v] ^ d[lca]`，就是 p4551Lca.cpp。
//
// ⇒ 剩下的问题变成：**n 个数里挑两个，异或最大**。01-Trie 从高位往低位贪心，O(31n)。
//
// ⚠ 两处要数清楚的：
//   ① 题面写 `0 ≤ w < 2^31` ⇒ 最高位是**第 30 位**（0 基），要跑 30..0 共 **31** 位。
//      写成 29..0 就丢最高位（p4551Bit.cpp）。
//   ② `d[u]` 和答案都 < 2^31 ⇒ `int` **恰好装得下，余量为 0**（和[第 37 章 P3378](/sol/p3378/) 同形）。
//
// ⚠ 建树用迭代 DFS：顶格 n = 10⁵ 排成一条链，递归**能活但只剩不到两倍余量**（见 p4551Rec.cpp）。
#include <bits/stdc++.h>
using namespace std;

const int BITS = 31;                                  // 第 30 位到第 0 位

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> head(n + 1, -1), nxt(2 * (n > 0 ? n : 1)), to(2 * (n > 0 ? n : 1)), wt(2 * (n > 0 ? n : 1));
    int ec = 0;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        to[ec] = v; wt[ec] = w; nxt[ec] = head[u]; head[u] = ec++;
        to[ec] = u; wt[ec] = w; nxt[ec] = head[v]; head[v] = ec++;
    }

    /* ① 迭代 DFS 求 d[] */
    vector<int> d(n + 1, 0);
    vector<char> vis(n + 1, 0);
    vector<int> st;
    st.push_back(1);
    vis[1] = 1;
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (vis[v]) continue;
            vis[v] = 1;
            d[v] = d[u] ^ wt[e];
            st.push_back(v);
        }
    }

    /* ② 01-Trie：n 个数里挑两个异或最大 */
    vector<array<int, 2>> ch(1);
    ch[0] = { 0, 0 };
    for (int i = 1; i <= n; i++) {
        int cur = 0;
        for (int b = BITS - 1; b >= 0; b--) {
            int t = (d[i] >> b) & 1;
            if (!ch[cur][t]) { ch.push_back({ 0, 0 }); ch[cur][t] = (int)ch.size() - 1; }
            cur = ch[cur][t];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int cur = 0, val = 0;
        for (int b = BITS - 1; b >= 0; b--) {
            int t = (d[i] >> b) & 1;
            if (ch[cur][t ^ 1]) { val |= 1 << b; cur = ch[cur][t ^ 1]; }
            else cur = ch[cur][t];
        }
        ans = max(ans, val);
    }
    cout << ans << '\n';
    return 0;
}

// P4551 —— ✗ 错法二：照搬[第 52 章树上差分](/ch/52-tree-diff/)那套**求和**的公式。
//
// ★ 那一章的路径和是：`s[u] + s[v] − 2·s[lca]`（根到 LCA 那一段被算了两遍，要减掉两遍）。
//   ⚠ 于是「异或版」顺手就写成 `d[u] ^ d[v] ^ d[lca]` —— 照猫画虎，减一遍。
//
// ★★ 而正确答案是**一遍都不减**：`x ^ x = 0`，那一段自己就抵消了。
//   ⇒ 多异或一个 `d[lca]`，等于**把根到 LCA 那一段又加了回去**。
//
// ⇒ ★★★ [第 52 章](/ch/52-tree-diff/)那条「上一章的正确写法可能就是这一章的 bug」又一次 ——
//   而这一次两章之间隔着的不是题目，是**运算**：加法要减两遍，异或一遍都不用。
//
// ⚠ 注意这一版**慢得多**（它要真的求 LCA，而且是 O(n²) 枚举点对），
//   所以只在小数据上当错法用 —— 这一页要看的是它**答什么**，不是它跑多快。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);
    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));
    }
    vector<int> d(n + 1, 0), fa(n + 1, 0), dep(n + 1, 0);
    vector<char> vis(n + 1, 0);
    vector<int> st(1, 1);
    vis[1] = 1;
    while (!st.empty()) {
        int u = st.back(); st.pop_back();
        for (size_t k = 0; k < g[u].size(); k++) {
            int v = g[u][k].first;
            if (vis[v]) continue;
            vis[v] = 1; d[v] = d[u] ^ g[u][k].second; fa[v] = u; dep[v] = dep[u] + 1; st.push_back(v);
        }
    }
    auto lca = [&](int x, int y) {
        while (dep[x] > dep[y]) x = fa[x];
        while (dep[y] > dep[x]) y = fa[y];
        while (x != y) { x = fa[x]; y = fa[y]; }
        return x;
    };
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) ans = max(ans, d[i] ^ d[j] ^ d[lca(i, j)]);   // ⚠ 多异或了一个
    cout << ans << '\n';
    return 0;
}

// P4551 —— ✗ 错法一：位数数错了，只做 30 位（第 29 位到第 0 位）。
//
// ★ 题面写的是 `0 ≤ w < 2^31`。
//   ⚠ 「小于 2³¹」很容易被读成「30 位」—— 而它其实是 **31 位**（第 30 位到第 0 位，
//     最大的 w 是 2³¹ − 1 = 2147483647，二进制是 31 个 1）。
//
// ★ 触发条件精确到一句话：**存在一对 (u, v) 使 `d[u] ^ d[v]` 的第 30 位是 1**。
//   ⚠ 而顺手写的生成器最爱把边权取成 `rng() % 1000` 这种小数
//   ⇒ 那一档是**结构性的精确的 0**（[第 46 章 P1100](/sol/p1100/) 那条：
//     **顺手写的上界正好卡在 bug 的下面**）。
#include <bits/stdc++.h>
using namespace std;

const int BITS = 30;                                  // ⚠ 少了一位

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> head(n + 1, -1), nxt(2 * (n > 0 ? n : 1)), to(2 * (n > 0 ? n : 1)), wt(2 * (n > 0 ? n : 1));
    int ec = 0;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        to[ec] = v; wt[ec] = w; nxt[ec] = head[u]; head[u] = ec++;
        to[ec] = u; wt[ec] = w; nxt[ec] = head[v]; head[v] = ec++;
    }
    vector<int> d(n + 1, 0);
    vector<char> vis(n + 1, 0);
    vector<int> st(1, 1);
    vis[1] = 1;
    while (!st.empty()) {
        int u = st.back(); st.pop_back();
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (vis[v]) continue;
            vis[v] = 1; d[v] = d[u] ^ wt[e]; st.push_back(v);
        }
    }
    vector<array<int, 2>> ch(1);
    ch[0] = { 0, 0 };
    for (int i = 1; i <= n; i++) {
        int cur = 0;
        for (int b = BITS - 1; b >= 0; b--) {
            int t = (d[i] >> b) & 1;
            if (!ch[cur][t]) { ch.push_back({ 0, 0 }); ch[cur][t] = (int)ch.size() - 1; }
            cur = ch[cur][t];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int cur = 0, val = 0;
        for (int b = BITS - 1; b >= 0; b--) {
            int t = (d[i] >> b) & 1;
            if (ch[cur][t ^ 1]) { val |= 1 << b; cur = ch[cur][t ^ 1]; }
            else cur = ch[cur][t];
        }
        ans = max(ans, val);
    }
    cout << ans << '\n';
    return 0;
}

// P4551 —— 三条路各做多少次基本操作，以及「int 到底够不够」那笔账。
//
// ★ 三条路：
//   ✗ 两两异或        C(n,2) 次 —— 顶格 10⁵ ⇒ **5×10⁹**
//   ★ 01-Trie         31 n 次插入 + 31 n 次查询 ⇒ 顶格 **6.2×10⁶**
//   ★ 按位分治        同样 O(31 n)，一行代码都不和 Trie 共享（顶格那一档的参照物）
//
// ★★ 而「要不要 long long」是一句除法就问完的事：
//   题面 `0 ≤ w < 2^31` ⇒ 每个 d[u] < 2^31，异或不会变大 ⇒ 答案 ≤ 2³¹ − 1
//   ⇒ **`int` 恰好装得下，余量为 0**（和[第 37 章 P3378](/sol/p3378/)、
//     [第 35 章 P1886](/sol/p1886/) 是同一个形状：题面把 int 的值域用满，一个格子都不剩）。
//   ⚠ 而这份程序顺手把它坐实：顶格随机边权下，**答案就是 2147483647 本身**。
//
// 用法：./p4551Count [table|csv]
#include <bits/stdc++.h>
using namespace std;

static string padLeft(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) { if ((c & 0xC0) == 0x80) continue; disp += (c < 0x80) ? 1 : 2; }
    return string(max(0, width - disp), ' ') + s;
}

static long long ops = 0;

static int trieMax(const vector<int>& d) {
    vector<array<int, 2>> ch(1);
    ch[0] = { 0, 0 };
    for (size_t i = 0; i < d.size(); i++) {
        int cur = 0;
        for (int b = 30; b >= 0; b--) {
            ops++;
            int t = (d[i] >> b) & 1;
            if (!ch[cur][t]) { ch.push_back({ 0, 0 }); ch[cur][t] = (int)ch.size() - 1; }
            cur = ch[cur][t];
        }
    }
    int ans = 0;
    for (size_t i = 0; i < d.size(); i++) {
        int cur = 0, val = 0;
        for (int b = 30; b >= 0; b--) {
            ops++;
            int t = (d[i] >> b) & 1;
            if (ch[cur][t ^ 1]) { val |= 1 << b; cur = ch[cur][t ^ 1]; }
            else cur = ch[cur][t];
        }
        ans = max(ans, val);
    }
    return ans;
}

static int bruteMax(const vector<int>& d) {
    int ans = 0;
    for (size_t i = 0; i < d.size(); i++)
        for (size_t j = i + 1; j < d.size(); j++) { ops++; ans = max(ans, d[i] ^ d[j]); }
    return ans;
}

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";
    const int NS[3] = { 1000, 4000, 16000 };
    long long tb[3][2];
    int ansSame = 1;
    for (int k = 0; k < 3; k++) {
        mt19937 rg(20260909u + k);
        vector<int> d(NS[k]);
        for (int i = 0; i < NS[k]; i++) d[i] = (int)(rg() & 0x7fffffffu);
        ops = 0; int a1 = bruteMax(d); tb[k][0] = ops;
        ops = 0; int a2 = trieMax(d);  tb[k][1] = ops;
        if (a1 != a2) ansSame = 0;
    }
    /* 顶格：答案顶到 int 的上限本身 */
    mt19937 rg(20260909u);
    vector<int> big(100000);
    for (int i = 0; i < 100000; i++) big[i] = (int)(rg() & 0x7fffffffu);
    int bigAns = trieMax(big);

    if (mode == "table") {
        printf("★ 基本操作次数（n 个数里挑两个异或最大）\n\n");
        printf("    %-8s %s %s\n", "n", padLeft("✗ 两两异或", 18).c_str(), padLeft("★ 01-Trie（31 位）", 22).c_str());
        for (int k = 0; k < 3; k++) printf("    %-8d %18lld %22lld\n", NS[k], tb[k][0], tb[k][1]);
        printf("    n 每翻 4 倍：两两异或 ×%.1f、×%.1f（O(n²) 的签名）；Trie ×%.1f、×%.1f（线性）\n",
               (double)tb[1][0] / tb[0][0], (double)tb[2][0] / tb[1][0],
               (double)tb[1][1] / tb[0][1], (double)tb[2][1] / tb[1][1]);
        printf("    ⇒ 顶格 n = 10⁵：两两异或 %lld 次，Trie %lld 次 —— 差 %.0f 倍\n\n",
               100000LL * 99999 / 2, 62LL * 100000,
               (100000.0 * 99999 / 2) / (62.0 * 100000));
        printf("★ 「int 够不够」：题面 0 ≤ w < 2³¹ ⇒ 答案 ≤ 2³¹ − 1 = 2147483647\n");
        printf("    顶格随机边权实测答案：%d ⇒ %s\n", bigAns,
               bigAns == 2147483647 ? "★ 正好顶到 int 的上限，余量为 0" : "没顶到");
        printf("    两两异或 ↔ Trie 三档答案一致：%s\n", ansSame ? "是" : "否");
    } else {
        for (int k = 0; k < 3; k++) printf("n%d,%lld %lld\n", NS[k], tb[k][0], tb[k][1]);
        printf("ansSame,%d\nbigAns,%d\n", ansSame, bigAns);
        printf("grow,%.1f %.1f %.1f %.1f\n",
               (double)tb[1][0] / tb[0][0], (double)tb[2][0] / tb[1][0],
               (double)tb[1][1] / tb[0][1], (double)tb[2][1] / tb[1][1]);
    }
    return 0;
}

// P4551 数据生成器（对拍用）。用法：./p4551Gen <seed> [档位] [n]，不给档位就是**最终档 2**。
//
// ★ 每个错法靠什么现形：
//   ①只做 30 位     ← 要「**某一对的异或第 30 位是 1**」
//                     ⚠ 而顺手写的边权是 `rng() % 1000` 这种小数 ⇒ 那一档是**结构性的 0**
//   ②照搬树上差分   ← 只要「最优的那一对的 LCA 不是根」，随机就抓
//
// 档位：
//   0  ★ 顺手写法：随机树，边权 0~999 —— ① 在这儿一次都碰不到
//   1  ★ 边权照题面顶格（0 ≤ w < 2^31）—— ① 这才有得谈
//   2  ★★ 最终档 = 1 ＋ 一半轮次造**链**（LCA 一定不是根，而且顺带压递归深度）
//   3  ★ 顶格链（配合 `n`）：给「递归会不会爆栈」和顶格秒表用
#include <bits/stdc++.h>
using namespace std;

static mt19937 rng;
static unsigned ru(unsigned m) { return rng() % m; }

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1u;
    int level = argc > 2 ? atoi(argv[2]) : 2;
    int n = argc > 3 ? atoi(argv[3]) : 0;
    rng.seed(seed * 2654435761u + 555u);
    if (n <= 0) n = (level == 3) ? 100000 : 6 + (int)ru(15);

    bool chain = (level == 3) || (level == 2 && (ru(2) == 0));
    printf("%d\n", n);
    for (int v = 2; v <= n; v++) {
        int u = chain ? v - 1 : 1 + (int)ru((unsigned)(v - 1));
        unsigned w;
        if (level == 0) w = ru(1000);
        else { w = rng(); w &= 0x7fffffffu; }            // 0 ≤ w < 2^31
        printf("%d %d %u\n", u, v, w);
    }
    return 0;
}