HDU – 5571 ：tree （动态点分治 异或）

题意：给定一棵树，有点权a[]，有边权。 现在有M次修改点权的操作，输出每次修改后，Σ(a[i]^a[j])*dis(i,j);

思路：因为待修改，我们需要快速得到以及修改一个点到其他所有点的信息。 肯定就是动态点分治了啊。

而异或这个操作没有什么累加的性质，所以每一位拆开单独计算。 根据二进制位置和01区别，先建立14*2点分树。然后每次在同一位置，不同值的树上累加答案。

因为计算dis的过程会重复很多次，所以可以用个dd数组，减少重复统计，然后就用1400ms变成 了960ms。

#include<bits/stdc++.h>
#define FOR() for(int i=Laxt[u];i;i=Next[i])
#define ll long long
#define rep(i,w,v) for(int i=w;i<=v;i++)
using namespace std;
const int maxn=;
int Laxt[maxn],Next[maxn<<],To[maxn<<],Len[maxn<<],cnt;
int a[maxn],sz[maxn],son[maxn],dep[maxn];
int Top[maxn],fa[maxn],Fa[maxn],vis[maxn],root,SZ;
ll G[maxn][][],F[maxn][][],ans,dis[maxn]; //
int num[maxn][][],mx;
void init(int N)
{
    cnt=; rep(i,,N) Laxt[i]=;
    rep(i,,N) vis[i]=; ans=;
    rep(i,,N) rep(j,,) rep(k,,)
       G[i][j][k]=F[i][j][k]=num[i][j][k]=;
}
void add(int u,int v,int len)
{
    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=len;
}
void dfs1(int u,int f)
{
    sz[u]=; dep[u]=dep[f]+; fa[u]=f; son[u]=;
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i]; if(v==f) continue;
        dis[v]=dis[u]+Len[i];
        dfs1(v,u); sz[u]+=sz[v];
        if(sz[son[u]]<sz[v]) son[u]=v;
    }
}
void dfs2(int u,int tp)
{
    Top[u]=tp;
    if(son[u]) dfs2(son[u],tp);
    FOR()
        if(To[i]!=fa[u]&&To[i]!=son[u])
            dfs2(To[i],To[i]);
}int LCA(int u,int v)
{
    while(Top[u]^Top[v]) dep[Top[u]]<dep[Top[v]]?v=fa[Top[v]]:u=fa[Top[u]];
    return dep[u]<dep[v]?u:v;
}
ll getdis(int u,int v){return dis[u]+dis[v]-*dis[LCA(u,v)];}
void Getroot(int u,int ff)
{
    sz[u]=;int ret=;
    FOR(){
        int v=To[i];if(v==ff||vis[v])continue;
        Getroot(v,u);sz[u]+=sz[v];
        ret=max(ret,sz[v]);
    }
    ret=max(ret,SZ-sz[u]);
    if(ret<mx) mx=ret,root=u;
}
void DFS(int u,int ff)
{
    vis[u]=true; Fa[u]=ff;
    FOR(){
        int v=To[i];if(vis[v])continue;
        mx=SZ=sz[v];
        Getroot(v,u);
        DFS(root,u);
    }
}
ll dd[maxn];
void Modify(int u,int val,int opt)
{
    int t;
    for(int j=u;Fa[j];j=Fa[j]) dd[j]=getdis(u,Fa[j]);
    rep(i,,){
        if(val&(<<i)) t=;
        else t=;
        ans=ans+1LL*opt*(<<i)*G[u][i][t^];
        for(int j=u;Fa[j];j=Fa[j]){
            ll d=dd[j];
            ans=ans+1LL*opt*(<<i)*(1LL*d*(num[Fa[j]][i][t^]-num[j][i][t^])+G[Fa[j]][i][t^]-F[j][i][t^]);
        }
    }
    rep(i,,){
        if(val&(<<i)) t=;
        else t=;
        num[u][i][t]+=opt;
        for(int j=u;Fa[j];j=Fa[j]){
            ll d=dd[j];
            G[Fa[j]][i][t]+=d*opt;
            F[j][i][t]+=d*opt;
            num[Fa[j]][i][t]+=opt;
        }
    }
}
int main()
{
    int N,Q,D,E,u,v,l;
    while(~scanf("%d",&N)){
        init(N);
        rep(i,,N) scanf("%d",&a[i]);
        rep(i,,N-){
            scanf("%d%d%d",&u,&v,&l);
            add(u,v,l); add(v,u,l);
        }
        dfs1(,); dfs2(,);
        SZ=mx=N; Getroot(,);
        DFS(root,);
        rep(i,,N) Modify(i,a[i],);
        scanf("%d",&Q);
        while(Q--){
            scanf("%d%d",&D,&E);
            Modify(D,a[D],-);
            a[D]=E;
            Modify(D,a[D],);
            printf("%lld\n",ans);
        }
    }
    return ;
}