【BZOJ-3589】动态树 树链剖分 + 线段树 + 线段覆盖（特殊的技巧）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
#define maxn 210000
int n,q;
struct Edgenode{int to,next;}edge[maxn<<1];
int head[maxn],cnt=1;
void add(int u,int v){cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt;}
void insert(int u,int v){add(u,v); add(v,u);}
//
//int fa[maxn],son[maxn],deep[maxn],size[maxn],pl[maxn],sz,pr[maxn],pre[maxn],top[maxn];
int fa[maxn],top[maxn],son[maxn];
int size[maxn],pl[maxn],pr[maxn],sz,pre[maxn],deep[maxn];
void dfs_1(int now)
{
    size[now]=1;
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=fa[now])
            {
                fa[edge[i].to]=now;
                deep[edge[i].to]=deep[now]+1;
                dfs_1(edge[i].to);
                if (size[son[now]]<size[edge[i].to]) son[now]=edge[i].to;
                size[now]+=size[edge[i].to];
            }
}
void dfs_2(int now,int chain)
{
    pl[now]=++sz;pre[sz]=now;top[now]=chain;
    if (son[now]) dfs_2(son[now],chain);
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=son[now] && edge[i].to!=fa[now])
            dfs_2(edge[i].to,edge[i].to);
    pr[now]=sz;
}
//
struct Treenode{int l,r,size,sum,tag;}tree[maxn<<3];
void update(int now)
{
    tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
}
void pushdown(int now)
{
    if (tree[now].tag)
        {
            tree[now<<1].tag+=tree[now].tag;tree[now<<1|1].tag+=tree[now].tag;
            tree[now<<1].sum+=tree[now].tag*tree[now<<1].size; 
            tree[now<<1|1].sum+=tree[now].tag*tree[now<<1|1].size;
            tree[now].tag=0;
        }
}
void build(int now,int l,int r)
{
    tree[now].l=l; tree[now].r=r; tree[now].size=r-l+1;
    tree[now].tag=0; tree[now].sum=0;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(now<<1,l,mid); build(now<<1|1,mid+1,r);
    update(now);
}
void change(int now,int L,int R,int D)
{
    pushdown(now);
    if (L<=tree[now].l && R>=tree[now].r) 
        {tree[now].sum+=D*tree[now].size; tree[now].tag+=D; return;}
    int mid=(tree[now].l+tree[now].r)>>1;
    if (L<=mid) change(now<<1,L,R,D);
    if (mid<R) change(now<<1|1,L,R,D);
    update(now);
}
int query(int now,int L,int R)
{
    pushdown(now);
    if (L<=tree[now].l && R>=tree[now].r) return tree[now].sum;
    int mid=(tree[now].l+tree[now].r)>>1,ans=0;
    if (L<=mid) ans+=query(now<<1,L,R);
    if (mid<R) ans+=query(now<<1|1,L,R);
//    printf("%d
",ans); puts("OK");
    return ans;
}
//
struct Linenode
{    
    int u,v;
    bool operator < (const Linenode & A) const
        {return u<A.u;}
}line[maxn]; int ln;
void AddLine(int x,int y)
{
    ln++;line[ln].u=x;line[ln].v=y;
}
void GetLine(int x,int y)
{
    while (top[x]!=top[y])
        {
            if (deep[top[x]]<deep[top[y]]) swap(x,y);
            AddLine(pl[top[x]],pl[x]);
            x=fa[top[x]];
        }
    if (deep[x]>deep[y]) swap(x,y);
    AddLine(pl[x],pl[y]);
}
void Ask()
{
    sort(line+1,line+ln+1);
    int L=line[1].u,R=line[1].v,ans=0;
    for (int i=2; i<=ln; i++)
        if (line[i].u>R) ans+=query(1,L,R),L=line[i].u,R=line[i].v;
            else R=max(R,line[i].v);
    ans+=query(1,L,R);
    printf("%d
",ans&2147483647);
}
//
int main()
{
//    freopen("data.in","r",stdin);
//    freopen("data.out","w",stdout);
    n=read();
    for (int u,v,i=1; i<=n-1; i++) u=read(),v=read(),insert(u,v);
    dfs_1(1); dfs_2(1,1); build(1,1,sz); 
//    for (int i=1; i<=n; i++) printf("%d %d %d %d %d
",i,pl[i],pr[i],top[i],son[i]);
    q=read();
    for (int i=1; i<=q; i++)
        {    
            int opt=read(),a,b,k;
            if (opt==0) {a=read(),b=read(),change(1,pl[a],pr[a],b);continue;}
            ln=0; k=read();
            for (int j=1; j<=k; j++) 
                a=read(),b=read(),GetLine(a,b);
            Ask();
        }
    return 0;
}