题意:单点set,树上路径异或和。

首先是 Nim 游戏的结论:异或和 0 为输,否则为赢。
考虑无修改情况,只需记录当前结点到根异或和,之后 dis[u] + dis[v] - dis[lca(u,v)] 即可。
考虑修改,注意到修改某一点的值相当于修改以当前点为根的子树的所有点的 dis。
即是 [dnum[u], dend[u]] 此段区间。dnum, dend 分别为 u 的 dfs 序编号,以及以 u 的根的子树的最远点编号。这时候进行区间异或。
查询 dis[u] + dis[v] - dis[lca(u,v)] + dis[fa(lca(u,v))]。
果断用数据结构维护。因为区间修改,单点查询可以差分后用 BIT 维护。
树剖肯定可以做,然而不想打。
记得!!!数组千万要开小点!!!!多开十倍即可 TLE !??
微笑[以为妙绝]
AFO!

码(116316K, 11936ms)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 5e5 + 100;
struct Edge
{
    int v, next;
    Edge(int a = 0, int b = 0) : v(a), next(b) {}
} pool[maxn * 2];
int pcnt = 1;
int header[maxn] = {0};
inline void add_edge(int u, int v) {pool[pcnt] = Edge(v, header[u]); header[u]=pcnt++;}

int BIT[maxn * 4] = {0};
int n;
inline void Bmodify(int a, int x){for(; a <= n; a += a & -a) BIT[a] ^= x;}
inline int Bquery(int a){int sum = 0; for(; a > 0; a -= a & -a) sum ^= BIT[a]; return sum;}

int dnum[maxn] = {0}, dclock = 1, pre = 0, dend[maxn] = {0};
int a[maxn] = {0};
int f[maxn][30] = {0}, depth[maxn] = {0}, dis[maxn] = {0};
int dfs(int u = 1, int fa = 0)
{
    f[u][0] = fa;
    dnum[u] = dend[u] = dclock++;
    dis[u] = dis[fa] ^ a[u];
    //dis2[dnum[u]] = dis[u];
    //dis3[dnum[u]] = dis[u] ^ pre;
    Bmodify(dnum[u], dis[u] ^ pre);
    pre = dis[u];
    for(int i = 1; i <= 20; i++)
        f[u][i] = f[f[u][i-1]][i-1];
    for(int i = header[u], v = pool[i].v; i; i = pool[i].next, v = pool[i].v)
        if(v != fa)
        {
            depth[v] = depth[u] + 1;
            dfs(v, u);
            dend[u] = max(dend[u], dend[v]);
        }
}
inline int lca(int u, int v)
{
    if(depth[u] < depth[v])
        swap(u, v);
    int delta = depth[u] - depth[v];
    for(int i = 0; i <= 20; i++)
        if((1 << i) & delta)
            u = f[u][i];
    if(u == v)
        return u;
    for(int i = 20; i >= 0; i--)
        if(f[u][i] != f[v][i])
            u = f[u][i], v = f[v][i];
    return f[u][0];
}

inline void change(int u, int v)
{
    int delta = v ^ Bquery(dnum[u]);
    if(u != 1)
        delta = Bquery(dnum[u]) ^ Bquery(dnum[f[u][0]]) ^ v;
    Bmodify(dnum[u], delta);
    Bmodify(dend[u] + 1, delta);
}
inline int query(int u, int v)
{
    int l = lca(u, v);
    if(l == 1)
        return Bquery(dnum[u]) ^ Bquery(dnum[v]) ^ Bquery(dnum[l]);
    return Bquery(dnum[u]) ^ Bquery(dnum[v]) ^ Bquery(dnum[l]) ^ Bquery(dnum[f[l][0]]);
}

int main()
{
    read(n);
    for(int i = 1; i <= n; i++)
        read(a[i]);
    int u, v;
    for(int i = 1; i < n; i++)
    {
        read(u, v);
        add_edge(u, v); add_edge(v, u);
    }
    dfs();
    int q; read(q);
    while(q--)
    {
        char ch[2]; scanf("%s", &ch);
        read(u, v);
        if(ch[0] == 'C') change(u, v);
        else printf("%s\n", query(u, v) == 0 ? "No" : "Yes");
    }
    return 0;
}

标签: bit, lca

添加新评论