题解：P4151 [WC2011] 最大 XOR 和路径

问我为什么放这张头图？我也不知道，纯想放。

Hints

Hint 1

答案路径呈一条链加上链上引出若干条连着一些环的路径的形状。

Hint 2

因为从链上的节点走到环上再走回链上的节点，所以用于连接环的路径不产生贡献。

Hint 3

若有两条从到的链，必然产生环，且两条路径的异或和异或起来恰好是这个环上的边的异或和。

Hint 4

异或空间线性基。

Solution

首先枚举所有环（事实上只需要枚举所有环的异或和的基即可），将它们的权值插入线性基，然后随便找一条链，查询线性基与这条链的异或和的最大异或和。

因为路径上链连到环的路径不产生贡献，所以我们只关注环，如果原链异或上一个与之边集无交的环，相当于引出来一条路径连着这个环，也就是 Hint 1 里的情况。

原链异或上一个边集有交集的环，相当于换了一条链，也就是 Hint 3 里的情况。

所以上述解法是正确的。

考虑一个问题，如何枚举所有环的异或和的基。

做法是，直接 dfs，对于每一条非树边，将其对应的环的异或和插入线性基。

证明如下：

证明

定义：

：根节点到节点的 dfs 树上路径边权异或和；
对任意边，权值为：
- 若为树边：；
- 若为非树边：定义基本环权值 （即代码插入线性基的值）。

任取取一个环 ,设环的节点序列为：

第条边，权值，环的总权值：。

对环上每条边分情况替换：

树边：。
非树边：。

将所有边权代入，拆式子：

$非树边$

设。

展开：

所有均成对抵消，所以。

将代入原式：

$非树边$

所以任意一个环的异或和均可以被 dfs 生成树上的基本环表出，证毕。

时间复杂度

dfs 生成树中有条非树边，单次插入复杂度，总计。

最后查询答案是的，忽略不计。

总计。

Code

#include <bits/stdc++.h>
#define nmf(i, s, e) for (int i = s; i <= e; i++)
#define ref(i, s, e) for (int i = s; i >= e; i--)
namespace FastIO
{
    template <typename T>
    inline void read(T &x)
    {
        short neg = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch))
            if (ch == '-')
                neg = -1;
        x = ch - '0';
        while (ch = getchar(), isdigit(ch))
            x = (x << 3) + (x << 1) + (ch ^ '0');
        x *= neg;
    }
    template <typename T, typename... Args>
    inline void read(T &x, Args &...args)
    {
        read(x);
        read(args...);
    }
    template <typename T>
    inline void read(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            read(*(begin + i));
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
            putchar('-'), x = -x;
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T, typename... Args>
    inline void write(T x, Args... args)
    {
        write(x);
        putchar(' ');
        write(args...);
    }
    template <typename T>
    inline void write(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            write(*(begin + i)), putchar(' ');
    }
}
using namespace FastIO;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;

class XORbasis
{
private:
    LL a[64];

public:
    XORbasis()
    {
        memset(a, 0, sizeof a);
    }
    void insert(LL x)
    {
        ref(i, 63, 0)
        {
            if (x >> i & 1)
            {
                if (!a[i])
                {
                    a[i] = x;
                    break;
                }
                else
                    x ^= a[i];
            }
        }
    }
    LL querymx(LL x)
    {
        LL ret = x;
        ref(i, 63, 0) if ((ret ^ a[i]) > ret) ret ^= a[i];
        return ret;
    }
    LL querymn(LL x)
    {
        LL ret = x;
        nmf(i, 0, 63) if ((ret ^ a[i]) < ret) ret ^= a[i];
        return ret;
    }
};
XORbasis B;
#define int LL
int n, m;
vector<pair<int, int>> grh[50004];
bool vis[50004];
int val[50004];
void dfs(int u, int now)
{
    vis[u] = 1;
    val[u] = now;
    for (auto [v, w] : grh[u])
    {
        if (vis[v])
            B.insert(now ^ val[v] ^ w);
        else
            dfs(v, now ^ w);
    }
}
void solve()
{
    read(n, m);
    nmf(i, 1, m)
    {
        int ui, vi, wi;
        read(ui, vi, wi);
        grh[ui].emplace_back(vi, wi);
        grh[vi].emplace_back(ui, wi);
    }
    dfs(1, 0);
    write(B.querymx(val[n]));
    return;
}
signed main()
{
    solve();
    return 0;
}