4034: [HAOI2015]树上操作
题目：传送门
题解：
树剖裸题：
麻烦一点的就只有子树修改（其实一点也不），因为子树编号连续啊，直接改段（记录编号最小和最大）
开个long long 水模版
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
struct node
{
int x,y,next;
}a[];int len,last[];
void ins(int x,int y)
{
len++;a[len].x=x;a[len].y=y;
a[len].next=last[x];last[x]=len;
}
struct trnode
{
int l,r,lc,rc;LL c,lz;
trnode(){lz=;}
}tr[];int trlen;
void update(int now)
{
if(tr[now].lz!=)
{
int lc=tr[now].lc,rc=tr[now].rc;
if(lc!=-)tr[lc].c+=LL(tr[lc].r-tr[lc].l+)*tr[now].lz,tr[lc].lz+=tr[now].lz;
if(rc!=-)tr[rc].c+=LL(tr[rc].r-tr[rc].l+)*tr[now].lz,tr[rc].lz+=tr[now].lz;
tr[now].lz=;
}
}
void bt(int l,int r)
{
int now=++trlen;
tr[now].l=l;tr[now].r=r;tr[now].c=;
tr[now].lc=tr[now].rc=-;
if(l<r)
{
int mid=(l+r)/;
tr[now].lc=trlen+;bt(l,mid);
tr[now].rc=trlen+;bt(mid+,r);
}
}
void change(int now,int l,int r,LL c)
{
if(tr[now].l==l && r==tr[now].r){tr[now].c+=LL(r-l+)*c;tr[now].lz+=c;return ;}
int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/;
update(now);
if(r<=mid)change(lc,l,r,c);
else if(mid+<=l)change(rc,l,r,c);
else change(lc,l,mid,c),change(rc,mid+,r,c);
tr[now].c=tr[lc].c+tr[rc].c;
}
LL getsum(int now,int l,int r)
{
if(tr[now].l==l && r==tr[now].r)return tr[now].c;
int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/;
update(now);
if(r<=mid)return getsum(lc,l,r);
else if(mid+<=l)return getsum(rc,l,r);
return getsum(lc,l,mid)+getsum(rc,mid+,r);
}
int n,m,fa[],tot[],son[],dep[];
void pre_tree_node(int x)
{
son[x]=;tot[x]=;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa[x])
{
fa[y]=x;dep[y]=dep[x]+;
pre_tree_node(y);
if(tot[y]>tot[son[x]])son[x]=y;
tot[x]+=tot[y];
}
}
}
int tp,id,ys[],top[],L[],R[];
void pre_tree_edge(int x,int tp)
{
ys[x]=++id;top[x]=tp;L[x]=id;
if(son[x]!=)pre_tree_edge(son[x],tp);
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=son[x] && y!=fa[x])pre_tree_edge(y,y);
}
R[x]=id;
}
LL sol(int x,int y)
{
LL ans=;int tx=top[x],ty=top[y];
while(tx!=ty)
{
if(dep[tx]>dep[ty])swap(tx,ty),swap(x,y);
ans+=getsum(,ys[ty],ys[y]);
y=fa[ty];ty=top[y];
}
if(x==y)return ans+getsum(,ys[x],ys[x]);
else
{
if(dep[x]>dep[y])swap(x,y);
return ans+getsum(,ys[x],ys[y]);
}
}
LL d[];
int main()
{
scanf("%d%d",&n,&m);len=;memset(last,,sizeof(last));
for(int i=;i<=n;i++)scanf("%lld",&d[i]);
for(int i=;i<n;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
fa[]=;dep[]=;pre_tree_node();
id=;pre_tree_edge(,);
trlen=;bt(,id);for(int i=;i<=n;i++)change(,ys[i],ys[i],d[i]);
while(m--)
{
int opt,x;LL y;scanf("%d",&opt);
if(opt==)scanf("%d%lld",&x,&y),change(,ys[x],ys[x],y);
else if(opt==)
{
scanf("%d%lld",&x,&y);
change(,L[x],R[x],y);
}
else {scanf("%d",&x);printf("%lld\n",sol(,x));}
}
return ;
}