题目描述

给定一棵 $n$ 个节点的点权树，$m$ 次查询两点间路径中，所有节点的权值的异或最大值。

输入格式

第一行两个数 $n, m$，表示树的节点数量和查询次数。

第二行 $n$ 个数描述树上每个节点的权值。

接下来 $n - 1$ 行描述树的边。

接下来 $m$ 行每行两个数，表示一个查询。

输出格式

输出共 $m$ 行，表示每次询问的答案。

输入样例：

4 2
11 5 7 9
1 2
1 3
1 4
2 3
1 4

输出样例：

14
11

离线点分治做法不太会，这里给个在线树剖做法。

算法

(树链剖分,ST表,线性基) $O((n + m) \log n \log ^ 2 \max G _ i)$

首先这题要求树上某条链属性，所以想到树剖。

因为树是静态的，所以想到用ST表/Trie。

Trie不太好求任意个元素异或最大值，故想到线性基。

然后这题就做完了

ST表的预处理中，需要将两个线性基合并为一个。考虑如何合并两个线性基。

因为线性基中最多会有 $\log$ 个元素，因此可以枚举其中一个基的所有元素，插入第二个基即可。

这部分代码及注释如下：

const int xbit = 60; // 最多需要的位数
// 线性基
struct vect
{
    ll x[xbit + 1]; // 基中所有元素

    // 辅助函数，返回第 t 个元素
    ll operator[] (const int t) const {return x[t];}

    // 求这组基中异或的最大值
    ll xor_max()
    {
        ll res = 0;
        for (int i = xbit; ~i; i -- )
            if ((res ^ x[i]) > res)
                res ^= x[i];
        return res;
    }

    // 插入一个数 t
    bool add(ll t)
    {
        for (int i = xbit; ~i; i -- )
            if (t >> i & 1)
                if (x[i]) t ^= x[i];
                else
                {
                    x[i] = t;
                    return true;
                }
    }

    // 插入一组基 t
    void add(const vect& t)
    {
        for (int i = xbit; ~i; i -- )
            if (t[i])
                add(t[i]);
    }
};

// 合并两个两个基
vect operator + (vect a, const vect& b)
{
    a.add(b);
    return a;
}

剩下的就是 ST 表和树剖板子了，见代码及注释。

时间复杂度

合并线性基的复杂度是 $O(\log ^ 2 \max G _ i)$。

预处理会合并 $O(n \log n)$ 次，故这部分复杂度是 $O(n \log n \log ^ 2 \max G _ i)$。

每次查询会合并 $O(\log n)$ 次，总共有 $q$ 次查询，故这部分复杂度是 $O(q \log n \log ^ 2 G _ i)$。

故总复杂度为 $O((n + q) \log n \log ^ 2 \max G _ i)$。

C++ 代码

#include <cstdio>
#include <cstring>

typedef long long ll;

const int xbit = 60; // 最多需要的位数
// 线性基
struct vect
{
    ll x[xbit + 1]; // 基中所有元素

    // 辅助函数，返回第 t 个元素
    ll operator[] (const int t) const {return x[t];}

    // 求这组基中异或的最大值
    ll xor_max()
    {
        ll res = 0;
        for (int i = xbit; ~i; i -- )
            if ((res ^ x[i]) > res)
                res ^= x[i];
        return res;
    }

    // 插入一个数 t
    bool add(ll t)
    {
        for (int i = xbit; ~i; i -- )
            if (t >> i & 1)
                if (x[i]) t ^= x[i];
                else
                {
                    x[i] = t;
                    return true;
                }
    }

    // 插入一组基 t
    void add(const vect& t)
    {
        for (int i = xbit; ~i; i -- )
            if (t[i])
                add(t[i]);
    }
};

// 合并两个两个基
vect operator + (vect a, const vect& b)
{
    a.add(b);
    return a;
}

const int N = 20005;
const int M = 400005;

int n, m;
int h[N], e[M], ne[M], idx;
int dep[N], top[N], fa[N], son[N];
int id[N], sz[N], scnt;
ll w[N], nw[N];

struct ST
{
    vect f[N][16];
    int lg2[N];

    // 预处理
    void build()
    {
        memset(f, 0, sizeof f);
        for (int i = 1; 1 << i <= n; i ++ ) lg2[1 << i] = 1;
        for (int i = 1; i <= n; i ++ ) lg2[i] += lg2[i - 1];
        for (int i = 1; i <= n; i ++ ) f[i][0].add(nw[i]);
        for (int k = 0; k < 16; k ++ )
            for (int i = 1; i + (1 << k) <= n; i ++ )
                f[i][k + 1] = f[i][k] + f[i + (1 << k)][k];
    }

    // 查区间 [l, r] 的基
    vect query(int l, int r)
    {
        int len = lg2[r - l + 1];
        return f[l][len] + f[r - (1 << len) + 1][len];
    }
} st;

void add(int a, int b)
{
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void dfs1(int u, int father, int depth)
{
    fa[u] = father, dep[u] = depth, sz[u] = 1;
    for (int i = h[u]; i; i = ne[i])
        if (e[i] != father)
        {
            dfs1(e[i], u, depth + 1);
            sz[u] += sz[e[i]];
            if (sz[e[i]] > sz[son[u]]) son[u] = e[i];
        }
}

void dfs2(int u, int t)
{
    id[u] = ++ scnt, nw[scnt] = w[u], top[u] = t;
    if (son[u])
    {
        dfs2(son[u], t);
        for (int i = h[u]; i; i = ne[i])
            if (e[i] != son[u] && e[i] != fa[u])
                dfs2(e[i], e[i]);
    }
}

// 查路径 a -> b 节点的权值的异或最大值
ll query(int a, int b)
{
    // res 存该路径中的基
    static vect res;
    memset(res.x, 0, sizeof res.x);
    while (top[a] != top[b])
    {
        if (dep[top[a]] < dep[top[b]]) a ^= b ^= a ^= b;
        res.add(st.query(id[top[a]], id[a]));
        a = fa[top[a]];
    }
    if (dep[a] < dep[b]) a ^= b ^= a ^= b;
    res.add(st.query(id[b], id[a]));
    return res.xor_max();
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", w + i);
    for (int i = 1; i < n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs1(1, 0, 0);
    dfs2(1, 1);
    st.build();
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%lld\n", query(a, b));
    }
    return 0;
}