http://www.lydsy.com/JudgeOnline/problem.php?id=3589
树链剖分
用线段数维护扫描线的方式来写,标记只打不下传
#include<cstdio>
#include<iostream>
#include<algorithm> #define N 200001 using namespace std;
int n; int front[N],to[N<<],nxt[N<<],tot; int siz[N],dep[N],fa[N];
int bl[N],in[N],out[N]; int sum[N<<],f[N<<];
int ans[N<<],tag[N<<]; int op[][]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;
} void dfs1(int x,int y)
{
siz[x]=;
for(int i=front[x];i;i=nxt[i])
{
if(to[i]==fa[x]) continue;
fa[to[i]]=x;
dep[to[i]]=dep[x]+;
dfs1(to[i],x);
siz[x]+=siz[to[i]];
}
} void dfs2(int x,int top)
{
bl[x]=top;
in[x]=++tot;
int y=;
for(int i=front[x];i;i=nxt[i])
if(to[i]!=fa[x] && siz[to[i]]>siz[y]) y=to[i];
if(!y) { out[x]=tot; return;}
dfs2(y,top);
for(int i=front[x];i;i=nxt[i])
if(to[i]!=fa[x] && to[i]!=y) dfs2(to[i],to[i]);
out[x]=tot;
} void down(int k,int l,int mid,int r)
{
sum[k<<]+=f[k]*(mid-l+);
sum[k<<|]+=f[k]*(r-mid);
f[k<<]+=f[k];
f[k<<|]+=f[k];
f[k]=;
} void add(int k,int l,int r,int opl,int opr,int w)
{
if(l>=opl && r<=opr)
{
sum[k]+=(r-l+)*w;
f[k]+=w;
return;
}
int mid=l+r>>;
if(f[k]) down(k,l,mid,r);
if(opl<=mid) add(k<<,l,mid,opl,opr,w);
if(opr>mid) add(k<<|,mid+,r,opl,opr,w);
sum[k]=sum[k<<]+sum[k<<|];
} void add_tag(int k,int l,int r,int opl,int opr,bool w)
{
if(l>=opl && r<=opr)
{
if(w) tag[k]++,ans[k]=sum[k];
else tag[k]--,ans[k]=;
return;
}
int mid=l+r>>;
if(f[k]) down(k,l,mid,r);
if(opl<=mid) add_tag(k<<,l,mid,opl,opr,w);
if(opr>mid) add_tag(k<<|,mid+,r,opl,opr,w);
if(!tag[k]) ans[k]=ans[k<<]+ans[k<<|];
else ans[k]=sum[k];
} void solve(int u,int v,bool ty)
{
while(bl[u]!=bl[v])
{
if(dep[bl[u]]<dep[bl[v]]) swap(u,v);
add_tag(,,n,in[bl[u]],in[u],ty);
u=fa[bl[u]];
}
if(dep[u]>dep[v]) swap(u,v);
add_tag(,,n,in[u],in[v],ty);
} int main()
{
freopen("data.in","r",stdin);
freopen("my.out","w",stdout);
read(n);
int u,v;
for(int i=;i<n;++i)
{
read(u); read(v);
add(u,v);
}
dfs1(,);
tot=;
dfs2(,);
int m;
read(m);
int ty;
while(m--)
{
read(ty);
if(!ty)
{
read(u); read(v);
add(,,n,in[u],out[u],v);
}
else
{
read(ty);
for(int i=;i<=ty;++i)
{
read(op[i][]); read(op[i][]);
solve(op[i][],op[i][],);
}
if(ans[]<) ans[]+=(1LL<<);
cout<<ans[]<<'\n';
for(int i=;i<=ty;++i) solve(op[i][],op[i][],);
}
}
}