P10799 题解

· · 题解

先考虑不在树上咋做。先给序列排序，然后一个一个判是否有 a_{i-1}+a_i>a_{i+1}。
如果不满足要求的话，那么对于所有 1<i<n 都有 a_{i-1}+a_i\le a_{i+1}。最小情况下 a_{i+1}=a_i+a_{i-1}，a_1=a_2=1。此时 a_i=f_i。但是你会发现 f_{46}>2^{31}-1，也就是说 n\ge46 就必定有解，非常 amazing 啊！只要对 <46 的区间暴力即可。
回到原题，查询只要先判路径长度再暴力跳即可。这部分是简单的，压力给到链异或单点查询。
容易发现，每次修改都能拆成四次到根链的修改。具体地，设 k=\operatorname{lca}(u,v)，则 u\to v 异或上 w 相当于 1\to u,1\to v,1\to k,1\to fa_k 异或上 w。但还是不好看，继续差分一下就能变成单点异或子树查，在 dfn 上建个树状数组即可。时间复杂度 O(n\log n+m\log n + mC\log C)，其中 C=46。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

vector<int> g[MAXN];

int n, a[MAXN], dep[MAXN], fa[20][MAXN];

int c[MAXN], in[MAXN], out[MAXN], id;

void init(int u, int f) {
    fa[0][u] = f, dep[u] = dep[f] + 1, in[u] = ++id, a[f] ^= a[u];
    for (int i = 1; i <= __lg(dep[u]); i++) fa[i][u] = fa[i - 1][fa[i - 1][u]];
    for (int v : g[u]) if (v != f) init(v, u); out[u] = id;
}

inline 
void add(int u, int x) {
    for (int i = in[u]; i <= n; i += i & -i) c[i] ^= x;
}

inline 
int ask(int u) {
    int res = 0;
    for (int i = out[u]; i; i &= i - 1) res ^= c[i];
    for (int i = in[u] - 1; i; i &= i - 1) res ^= c[i];
    return res;
}

inline 
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (; dep[u] > dep[v]; u = fa[__lg(dep[u] - dep[v])][u]);
    if (u == v) return u;
    for (int i = __lg(dep[u]); ~i; i--) {
        if (fa[i][u] != fa[i][v]) u = fa[i][u], v = fa[i][v];
    }
    return fa[0][u];
}

inline 
vector<int> get(int u, int v) {
    vector<int> d;
    if (dep[u] < dep[v]) swap(u, v);
    for (; dep[u] > dep[v]; d.emplace_back(ask(u)), u = fa[0][u]);
    for (; u != v; ) {
        d.emplace_back(ask(u)), u = fa[0][u];
        d.emplace_back(ask(v)), v = fa[0][v];
    }
    return d.emplace_back(ask(u)), d;
}

inline 
bool check(vector<int> d) {
    sort(d.begin(), d.end()); int m = d.size();
    for (int i = 1; i < m - 1; i++) {
        if (d[i - 1] > d[i + 1] - d[i]) return 1;
    }
    return 0;
}

inline 
void modify(int u, int v, int w) {
    int k = lca(u, v);
    add(u, w), add(v, w), add(k, w);
    if (fa[0][k]) add(fa[0][k], w);
}

inline 
bool query(int u, int v) {
    int k = lca(u, v);
    if (dep[u] + dep[v] - 2 * dep[k] + 1 > 46) return 1;
    else return check(get(u, v));
}

int m;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        g[u].emplace_back(v), g[v].emplace_back(u);
    }
    init(1, 0);
    for (int i = 1; i <= n; i++) add(i, a[i]);
    for (int opt, u, v, w; m--;) {
        scanf("%d%d%d", &opt, &u, &v);
        if (opt == 1) scanf("%d", &w), modify(u, v, w);
        else printf("%d", query(u, v));
    }
}