[SCOI2016]幸运数字

LG传送门

为了快乐，我们用树剖写这题。

强行树剖，线段树上每个结点维护一个线性基，每次查询暴力合并。

瞎分析一波复杂度：树剖两点之间\(\log n\)条重链，每条重链在线段树上最多合并\(\log n\)次，合并两个线性基最多需要\(\log m\)次插入，每次插入\(\log m\)（设\(m\)为值域）。总复杂度大概是\(O(n (\log n) ^ 2 (\log m) ^ 2)\)可能错了不要怪我。

算起来大概是\(1.62 * 10 ^ {10}\)的规模，但是我们是有信仰的oier，我们要坚信这个东西是跑不满的。所以我就最慢的点\(1.1s\)多过了这题。当然不吸氧是布星的。

//written by newbiechd

#include <cstdio>

#include <cctype>

#include <vector>

#define R register

#define I inline

#define B 1000000

#define L long long

using namespace std;

const int N = 20003;

char buf[B], *p1, *p2;

I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++; }

I L rd() {

    L f = 0;

    R char c = gc();

    while (c < 48 || c > 57)

        c = gc();

    while (c > 47 && c < 58)

        f = f * 10 + (c ^ 48), c = gc();

    return f;

}

int s[N], fa[N], dep[N], siz[N], son[N], dfn[N], top[N], n, tim;

L w[N], val[N];

vector <int> g[N];

I L min(L x, L y) { return x < y ? x : y; }

I L max(L x, L y) { return x > y ? x : y; }

I void swap(L &x, L &y) { x ^= y, y ^= x, x ^= y; }

I void swap(int &x, int &y) { x ^= y, y ^= x, x ^= y; }

struct base {

    vector <L> v;

    I void insert(L x) {

        R int i, s = v.size();

        for (i = 0; i < s; ++i)

            x = min(x, x ^ v[i]);

        if (x) {

            v.push_back(x);

            for (i = s; i; --i)

                if (v[i] > v[i - 1])

                    swap(v[i], v[i - 1]);

        }

    }

    I void merge(base x) {

        for (R int i = 0, s = x.v.size(); i < s; ++i)

            insert(x.v[i]);

    }

    I L query() {

        L o = 0;

        for (R int i = 0, s = v.size(); i < s; ++i)

            o = max(o, o ^ v[i]);

        return o;

    }

}e[N << 2], ans;

void dfs1(int x, int f) {

    fa[x] = f, dep[x] = dep[f] + 1, siz[x] = 1;

    for (R int i = 0, y, m = 0; i < s[x]; ++i)

        if ((y = g[x][i]) ^ f) {

            dfs1(y, x), siz[x] += siz[y];

            if (siz[y] > m)

                m = siz[y], son[x] = y;

        }

}

void dfs2(int x, int t) {

    dfn[x] = ++tim, val[tim] = w[x], top[x] = t;

    if (son[x])

        dfs2(son[x], t);

    for (R int i = 0, y; i < s[x]; ++i)

        if ((y = g[x][i]) ^ fa[x] && y ^ son[x])

            dfs2(y, y);

}

void build(int k, int l, int r) {

    for (R int i = l; i <= r; ++i)

        e[k].insert(val[i]);

    if (l == r)

        return ;

    R int p = k << 1, q = p | 1, m = (l + r) >> 1;

    build(p, l, m), build(q, m + 1, r);

}

void tquery(int k, int l, int r, int x, int y) {

    if (x <= l && r <= y) {

        ans.merge(e[k]);

        return ;

    }

    R int p = k << 1, q = p | 1, m = (l + r) >> 1;

    if (x <= m)

        tquery(p, l, m, x, y);

    if (m < y)

        tquery(q, m + 1, r, x, y);

}

I L query(int x, int y) {

    ans.v.clear();

    while (top[x] ^ top[y]) {

        if (dep[top[x]] < dep[top[y]])

            swap(x, y);

        tquery(1, 1, n, dfn[top[x]], dfn[x]), x = fa[top[x]];

    }

    if (dep[x] > dep[y])

        swap(x, y);

    tquery(1, 1, n, dfn[x], dfn[y]);

    return ans.query();

}

int main() {

    R int Q, i, x, y;

    n = rd(), Q = rd();

    for (i = 1; i <= n; ++i)

        w[i] = rd();

    for (i = 1; i < n; ++i)

        x = rd(), y = rd(), g[x].push_back(y), g[y].push_back(x);

    for (i = 1; i <= n; ++i)

        s[i] = g[i].size();

    dfs1(1, 0), dfs2(1, 1), build(1, 1, n);

    for (i = 1; i <= Q; ++i)

        x = rd(), y = rd(), printf("%lld\n", query(x, y));

    return 0;

}

有\(O(n \log n \log m)\)的点分治写法，但是我懒得写了。