P3401 「洛谷树」

原题链接

题目描述

第一行两个正整数 和 ，表示点的个数，查询和询问的总次数。

接下来 行，每行两个正整数 和一个非负整数 ，表示 和 两个点之间有一条边权为 的边。

接下来 行，格式为 1 u v 或 2 u v w。
如果为 1 u v 操作，你需要输出 到 的路径上所有子路径经过的边的边权的 值的和是多少。
如果为 2 u v w 操作，你需要把 到 这条边的边权改为 ，保证这条边存在。

输出格式

对于每个 操作，输出答案。

SAMPLE I/O

I

5 3
1 2 3
2 3 3
2 4 6
4 5 1
1 3 4
2 2 4 7
1 3 5

O

14
26

对于 的数据，所有边权小于等于 。

思路

首先看到题面，是非常典型的树链剖分模板，于是我们可以考虑使用树链剖分。发现，如果没有“路径上所有子路径经过的边的边权”的话，那么他就是一道裸的树链剖分。加入了这个条件，我们就看怎么把他转化掉。

从 到 的路径上，要查找从 到 的异或和值，除了普通的树链剖分跳链，还可以用一种更为直接的方法：预处理从 （根节点）到每一个点的路径上的异或和，记为 ，再计算 即可。

如何证明这个结论？注意到对于同一个数 ，。所以从 到 的这些路径都会被异或成 ，所以会被计算的就只有从 到 的路径了。于是乎问题就被转化成了：从 到 的任意两点之间路径异或和的和。

注意到题目描述的最后一行：对于100% 的数据，所有边权小于等于 1023。数值非常小而且正好是 。并且又是关于异或的运算，于是考虑把每一位拆开来看。我们回顾异或的基本性质：两个位不同则答案为1，否则为0。对于答案为 的情况，我们只看第 位，找出从 到 中的边权中该位为 的边个数 和边权中该位为 的边个数 。则这些对答案的贡献就是 。因为把不同的 放入不同的 的搭配数就是 的个数和 的个数的乘积（这个小学就学过了吧，就是那种不同帽子搭配不同衣服的搭配数的问题）。然后再把所有位的贡献加起来就是答案了。

还没完！！！还有修改！！！修改边的话就用树链剖分常用的边转点。注意到我们维护的是上面提到的从 到 的异或和 ，根据上面的定义，

$${val_u = {w_u} \oplus {w_{fa_u}} \oplus {w_{fa_{fa_u}}} \oplus \cdots \oplus {w_{root}} }$$

就是把这个点以及其所有的祖先全部异或起来的值。我们要修改 ，就把之前 的贡献撤销，再异或一个新的贡献 ，所以要修改这个点的 就直接用 即可。但是考虑到这个点的儿子、孙子等等也用了 的贡献，所以也要把他们给改了，相当于是把以这个点为根的子树全部异或 。

最后，对于每一个 ，开一个长度大小为 的数组来维护每一位的 值即可。

代码如下：

学生代码写4K

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct bit{
    int a[10];
    bit() {for(int i=0;i<10;i++) a[i] = 0;}
};
const int N = 3e4+4;
struct node{
    int l, r;
    bit val, lazy;//val存储的是这个区间的第i位的“1”的个数
}tr[N<<2];

struct Edge{
    int to, nxt, w;
}edge[N<<1];
int h[N], cnt;
void _add(int u, int v, int w){
    edge[++cnt] = {v, h[u], w};
    h[u] = cnt;
}
void add(int u, int v, int w){
    _add(u, v, w), _add(v, u, w);
}

void modify(int x, int y){//将线段树上的x这个区间的第y位异或之
    tr[x].val.a[y] = (tr[x].r - tr[x].l + 1) - tr[x].val.a[y];
    tr[x].lazy.a[y] ^= 1;
}

bit operator +(const bit &x, const bit &y){
    bit z;
    for(int i=0;i<10;i++){
        z.a[i] = x.a[i] + y.a[i];
    }
    return z;
}

void pushup(int x){
    tr[x].val = tr[x<<1].val + tr[x<<1|1].val;
}

void pushdown(int x){
    for(int i=0;i<10;i++){
        if(tr[x].lazy.a[i]){
            modify(x<<1, i);
            modify(x<<1|1, i);
            tr[x].lazy.a[i] = 0;
        }
    }
}

int w[N], wnew[N];

int pre[N], prenew[N];

void build(int x, int l, int r){
    tr[x].l = l, tr[x].r = r;
    if(l==r){
        for(int i=0;i<10;i++){
            tr[x].val.a[i] = (prenew[l]>>i)&1;
            tr[x].lazy.a[i] = 0;
        }
        return ;
    }
    int mid = l+r>>1;
    build(x<<1, l, mid);
    build(x<<1|1, mid+1, r);
    pushup(x);
}

void change(int x, int ql, int qr, int w){
    int l = tr[x].l, r = tr[x].r;
    if(ql<=l&&r<=qr){
        for(int i=0;i<10;i++){
            if(w>>i&1) modify(x, i);
        }
        return ;
    }
    pushdown(x);
    int mid = l+r>>1;
    if(ql<=mid) change(x<<1, ql, qr, w);
    if(qr>mid) change(x<<1|1, ql, qr, w);
    pushup(x);
}

bit query(int x, int ql, int qr){
    int l = tr[x].l, r = tr[x].r;
    if(ql<=l&&r<=qr){
        return tr[x].val;
    }
    pushdown(x);
    int mid = l+r>>1;
    bit ans;
    if(ql<=mid) ans = query(x<<1, ql, qr);
    if(qr>mid) ans = ans + query(x<<1|1, ql, qr);
    return ans;
}


int siz[N], top[N], dep[N], fa[N], son[N], id[N], dfn;

void dfs1(int x, int father){
    fa[x] = father;
    dep[x] = dep[father] + 1;
    siz[x] = 1;
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(v==father) continue;
        w[v] = edge[i].w;
        pre[v] = pre[x] ^ w[v];
        dfs1(v, x);
        siz[x] += siz[v];
        if(!son[x]||siz[son[x]] < siz[v])
            son[x] = v;
    }
}

void dfs2(int x, int topx){
    top[x] = topx;
    id[x] = ++dfn;
    wnew[dfn] = w[x];
    prenew[dfn] = pre[x];
    if(!son[x]) return ;
    dfs2(son[x], topx);
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(v!=fa[x]&&v!=son[x]) dfs2(v, v);
    }
}


ll queryans(int x, int y){
    bit ans;
    int stx = x, sty = y;
    while(top[x]!=top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        ans = ans + query(1, id[top[x]], id[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    ans = ans + query(1, id[x], id[y]);
    ll ansnum = 0;
    for(int i=0;i<10;i++){
        ll count1 = ans.a[i];
        ll count0 = dep[stx] + dep[sty] - 2*dep[x] + 1 - count1;
        ansnum += (1ll<<i)*count1*count0;
    }
    return ansnum;
}
int n, q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>q;
    int u, v, ww;
    for(int i=1;i<n;i++){
        cin>>u>>v>>ww;
        add(u, v, ww);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    
    int op;
    while(q--){
        cin>>op>>u>>v;
        if(op==1){
            cout<<queryans(u, v)<<'\n';
        }else{
            cin>>ww;
            if(dep[u] < dep[v]) swap(u, v);
            change(1, id[u], id[u]+siz[u]-1, ww^w[u]);
            w[u] = ww;
        }
    }
    return 0;
    
}