2020 Multi-University Training Contest 3---- HDU--6793、Tokitsukaze and Colorful Tree（离线+树状数组）

题面：

题意：
给定一棵树，根节点为1，每个点有颜色和权值两个属性。
我有两种操作，更改某个点的颜色或者更改某个点的权值。
询问每次更改之后 $<munder> \sum c o l o r [x] = = c o l o r [y] <mtext> </mtext> a n d <mtext> </mtext> x, y 互不为祖先 </munder> v a l [x] <mtext> </mtext> x o r <mtext> </mtext> v a l [y]$ 。

题解：
对于每一种颜色的贡献都是独立的，所以我们可以枚举每种颜色对答案的贡献。
对于相同颜色的节点，每一位的贡献都是独立的，所以我们可以再去枚举每一位的贡献。
我们设 $a n s [i]$ 为第 $i$ 次修改后所要求的 $s u m$ 的变化值。
那么我们最后再对 $a n s [i]$ 求一遍前缀和即为答案。

考虑对于某一种颜色怎么维护这种颜色对 $a n s [i]$ 的贡献。
我们将修改拆分为一次删除（某种颜色或者某个权值）和一次增加（某种颜色或者某个权值）。
考虑当前枚举到 $c o l o r$ 颜色，第 $k$ 位， $x$ 节点。

我们考虑这一次在 $x$ 节点操作的贡献。
现在我们正在维护的颜色都是 $c o l o r$ ，正在搞第 $k$ 位。
那么我们需要知道不在根节点到 $x$ 节点上，不在 $x$ 节点的子树中的 0/1 的数量。
我们设 $c = (x > > k) & 1$ ，那么这一位的贡献就为:
$a n s [i d] + = (1 < < k) * c n t (c <mtext> </mtext> x o r <mtext> </mtext> 1) * o p$
其中 $i d$ 为这一次操作是哪一次修改形成的。
$c n t (c <mtext> </mtext> x o r <mtext> </mtext> 1)$ 不在根节点到 $x$ 节点上，不在 $x$ 节点的子树中的 $c <mtext> </mtext> x o r <mtext> </mtext> 1$ 的数量。
$o p$ 为这一次操作时删除操作还是增加操作。

那么我们只需要求解出不在根节点到 $x$ 节点上，不在 $x$ 节点的子树中的 0/1 的数量即可。

这个数量可以用总的0/1的数量减去在根节点到 $x$ 节点上，在 $x$ 节点的子树中的 0/1 的数量。
可以用树剖维护，总的时间复杂度大概是 $O (20 * n l o g^{2} n)$

上述时间复杂度有点大。
我们考虑 $d f s$ 序上建立树状数组。

我们建立两类树状数组，每一类都维护0/1的个数。
对于第一类，我们修改时只修改当前节点 $s t [x]$ 的贡献，表示 $x$ 节点点出的贡献发生变化。
对于第二类，我们修改时利用差分的思想，在 $s t [x]$ 位置处加上贡献，在 $e d [x] + 1$ 位置处减去贡献，将对节点的修改转化为对子树的修改。

考虑查询：
当前节点为 $x$ 。
那么我们在第一类树状数组上查询 $[s t [x], e d [x]]$ ，即在 $x$ 节点的子树中的 0/1 的数量。
在第二类树状数组上查询 $s t [x]$ ，即 $x$ 点的祖先节点中产生的贡献，即根节点到 $x$ 节点0/1的数量。

总的时间复杂度为 $O (20 * n l o g n)$

还需要注意，两种颜色切换时要清空树状数组。
这里为了避免每次清空树状数组所带来的时间复杂度过大，我们只需要把当前颜色 $c o l o r$ 所有的节点的权值从树状数组中删掉即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=30;

int head[maxn],ver[maxn<<1],nt[maxn<<1],tot=1;
int val[maxn],color[maxn];
int st[maxn],ed[maxn],si[maxn],cnt=0;
int fa[2][maxn],son[2][maxn];
//fa[0] 根节点到x路径上0的个数，fa[1]根节点到x路径上1的个数
//son[0] 节点x的子树中0的个数，son[1] 节点x的子树中1的个数。
ll ans[maxn];
struct node
{
    int x,valx;
    int id,op;
    node(){}
    node(int a,int b,int c,int d)
    {
        x=a,valx=b,id=c,op=d;
    }
};
vector<node>vc[maxn];

void init(int n)
{
    tot=1,cnt=0;
    for(int i=1;i<=n;i++)
    {
        head[i]=0;
        vc[i].clear();
    }
}

void addedge(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void dfs(int x,int fa)
{
    si[x]=1;
    st[x]=++cnt;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        dfs(y,x);
        si[x]+=si[y];
    }
    ed[x]=cnt;
}

void add(int *c,int x,int val)
{
    for(;x<=cnt;x+=(x&(-x)))
        c[x]+=val;
}

int ask(int *c,int x)
{
    int ans=0;
    for(;x;x-=(x&(-x)))
        ans+=c[x];
    return ans;
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        int n,x,y;
        scanf("%d",&n);
        init(n);
        for(int i=1;i<=n;i++)
            scanf("%d",&color[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&val[i]);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            addedge(x,y);
            addedge(y,x);
        }
        dfs(1,0);

        for(int i=1;i<=n;i++)
            vc[color[i]].pb(node(i,val[i],0,1));

        int q,op;
        scanf("%d",&q);
        for(int i=0;i<=q;i++)
            ans[i]=0;

        for(int i=1;i<=q;i++)
        {
            scanf("%d%d%d",&op,&x,&y);
            vc[color[x]].pb(node(x,val[x],i,-1));
            if(op==1)
                val[x]=y;
            else color[x]=y;
            vc[color[x]].pb(node(x,val[x],i,1));
        }

        for(int i=1;i<=n;i++)
            vc[color[i]].pb(node(i,val[i],q+1,-1));

        for(int i=1;i<=n;i++)//枚举颜色
        {
            for(int k=0;k<20;k++)//枚举哪一位
            {
                for(auto now:vc[i])//枚举该颜色的所有的点，这些点已经是按照时间顺序存储的
                {
                    int res=0;
                    if((now.valx>>k)&1)
                    {
                        res=ask(son[0],cnt);//整棵树上所有的0 1--cnt
                        res-=ask(son[0],ed[now.x])-ask(son[0],st[now.x]);//x节点子树中的0(不包括x节点)
                        //这里下面这种写法也可，因为 st[now.x]没有贡献
                        //res-=ask(son[0],ed[now.x])-ask(son[0],st[now.x]-1);
                        res-=ask(fa[0],st[now.x]);//x节点及其父亲中的0
                    }
                    else
                    {
                        res=ask(son[1],cnt);//整棵树上所有的1 1--cnt
                        res-=ask(son[1],ed[now.x])-ask(son[1],st[now.x]);//x节点子树中的1（不包括x节点）
                        //这里下面这种写法也可，因为 st[now.x]没有贡献
                        //res-=ask(son[1],ed[now.x])-ask(son[1],st[now.x]-1);
                        res-=ask(fa[1],st[now.x]);//x节点及其父亲中的1
                    }
                    ans[now.id]+=1ll*(1<<k)*res*now.op;
                    add(son[(now.valx>>k)&1],st[now.x],now.op);
                    add(fa[(now.valx>>k)&1],st[now.x],now.op);
                    add(fa[(now.valx>>k)&1],ed[now.x]+1,-now.op);
                }
            }
        }
        for(int i=1;i<=q;i++)
            ans[i]+=ans[i-1];
        for(int i=0;i<=q;i++)
            printf("%lld\n",ans[i]);
    }
    return 0;
}