BZOJ3589 动态树（树链剖分+容斥原理）

　　显然容斥后转化为求树链的交。这个题非常良心的保证了查询的路径都是到祖先的，求交就很休闲了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 200010

#define ui unsigned int

#define inf ((ui)4294967295)

#define p31 2147483647

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,p[N],fa[N],deep[N],son[N],size[N],top[N],dfn[N],L[N<<],R[N<<],u[],v[],flag[],k,cnt,t;

ui tree[N<<],lazy[N<<],ans;

struct data{int to,nxt;

}edge[N<<];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

void dfs1(int k)

{

    size[k]=;

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=fa[k])

    {

        fa[edge[i].to]=k;

        deep[edge[i].to]=deep[k]+;

        dfs1(edge[i].to);

        size[k]+=size[edge[i].to];

        if (size[edge[i].to]>size[son[k]]) son[k]=edge[i].to;

    }

}

void dfs2(int k,int from)

{

    dfn[k]=++cnt;top[k]=from;

    if (son[k]) dfs2(son[k],from);

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=fa[k]&&edge[i].to!=son[k]) dfs2(edge[i].to,edge[i].to);

}

void build(int k,int l,int r)

{

    L[k]=l,R[k]=r;

    if (l==r) return;

    int mid=l+r>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

}

void up(int k){tree[k]=tree[k<<]+tree[k<<|];}

void update(int k,ui x){tree[k]+=(R[k]-L[k]+)*x,lazy[k]+=x;}

void down(int k){update(k<<,lazy[k]),update(k<<|,lazy[k]),lazy[k]=;}

void add(int k,int l,int r,ui x)

{

    if (L[k]==l&&R[k]==r){update(k,x);return;}

    if (lazy[k]) down(k);

    int mid=L[k]+R[k]>>;

    if (r<=mid) add(k<<,l,r,x);

    else if (l>mid) add(k<<|,l,r,x);

    else add(k<<,l,mid,x),add(k<<|,mid+,r,x);

    up(k);

}

ui query(int k,int l,int r)

{

    if (L[k]==l&&R[k]==r) return tree[k];

    if (lazy[k]) down(k);

    int mid=L[k]+R[k]>>;

    if (r<=mid) return query(k<<,l,r);

    else if (l>mid) return query(k<<|,l,r);

    else return query(k<<,l,mid)+query(k<<|,mid+,r);

}

ui sum(int x,int y)

{

    ui ans=;

    while (top[x]!=top[y])

    {

        if (deep[top[x]]<deep[top[y]]) swap(x,y);

        ans+=query(,dfn[top[x]],dfn[x]);

        x=fa[top[x]];

    }

    if (deep[x]<deep[y]) swap(x,y);

    ans+=query(,dfn[y],dfn[x]);

    return ans;

}

int lca(int x,int y)

{

    while (top[x]!=top[y])

    {

        if (deep[top[x]]<deep[top[y]]) swap(x,y);

        x=fa[top[x]];

    }

    if (deep[x]<deep[y]) swap(x,y);

    return y;

}

bool in(int x,int y){return dfn[x]<=dfn[y]&&dfn[x]+size[x]->=dfn[y];}

void calc(int op)

{

    int x=,y=;

    for (int i=;i<=k;i++)

    if (flag[i])

    {

        if (!x) x=u[i],y=v[i];

        else

        {

            int p=u[i],q=v[i];

            if (deep[x]>deep[p]) swap(x,p),swap(y,q);

            if (in(x,p)&&in(p,y)) x=p,y=lca(y,q);

            else return;

        }

    }

    if (x==) return;

    else if (op>) ans+=sum(x,y);

    else ans+=inf-sum(x,y)+;

}

void dfs(int cur,int op)

{

    if (cur>k) {calc(op);return;}

    flag[cur]=;dfs(cur+,-op);

    flag[cur]=;dfs(cur+,op);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3589.in","r",stdin);

    freopen("bzoj3589.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<n;i++)

    {

        int x=read(),y=read();

        addedge(x,y),addedge(y,x);

    }

    dfs1();

    dfs2(,);

    build(,,n);

    int m=read();

    while (m--)

    {

        int op=read();

        if (op==)

        {

            int x=read(),y=read();

            add(,dfn[x],dfn[x]+size[x]-,y);

        }

        if (op==)

        {

            k=read();ans=;

            for (int i=;i<=k;i++) u[i]=read(),v[i]=read();

            for (int i=;i<=k;i++) if (dfn[u[i]]>dfn[v[i]]) swap(u[i],v[i]);

            dfs(,-);printf("%u\n",ans&p31);

        }

    }

    return ;

}