有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:操作 1 :把某个节点 x 的点权增加 a 。操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 :询问某个节点 x 到根的路径中所有点的点权和。
输入格式:
第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数,表示树中节点的初始权值。接下来 N-1 行每行两个正整数 from, to , 表示该树中存在一条边 (from, to) 。再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x a ) 。
输出格式:
对于每个询问操作,输出该询问的答案。答案之间用换行隔开。
输入样例#1:
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
输出样例#1:
6
9
13
对于 100% 的数据, N,M<=100000 ,且所有输入数据的绝对值都不
会超过 10^6 。
树链剖分的裸题
每次暴力更改就好
注意这题需要开long long
#include<iostream>
#include<cstdio>
#include<cstring>
#define ls k<<1
#define rs k<<1|1
#define LL long long
using namespace std;
const LL MAXN=1e6+10;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p1=(p2=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:++*p1;
}
inline LL read()
{
char c=getchar();LL x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
return x*f;
}
LL root=1;
struct node
{
LL u,v,w,nxt;
}edge[MAXN];
LL head[MAXN];
LL num=1;
inline void AddEdge(LL x,LL y)
{
edge[num].u=x;
edge[num].v=y;
edge[num].nxt=head[x];
head[x]=num++;
}
struct Tree
{
LL l,r,f,w,siz;
}T[MAXN];
LL a[MAXN],b[MAXN],tot[MAXN],idx[MAXN],deep[MAXN],son[MAXN],top[MAXN],fa[MAXN],cnt=0;
void update(LL k)
{
T[k].w=T[ls].w+T[rs].w;
}
void PushDown(LL k)
{
if(!T[k].f) return ;
T[ls].w+=T[k].f*T[ls].siz;
T[rs].w+=T[k].f*T[rs].siz;
T[ls].f+=T[k].f;
T[rs].f+=T[k].f;
T[k].f=0;
}
LL dfs1(LL now,LL f,LL dep)
{
deep[now]=dep;
tot[now]=1;
fa[now]=f;
LL maxson=-1;
for(LL i=head[now];i!=-1;i=edge[i].nxt)
{
if(edge[i].v==f) continue;
tot[now]+=dfs1(edge[i].v,now,dep+1);
if(tot[edge[i].v]>maxson) maxson=tot[edge[i].v],son[now]=edge[i].v;
}
return tot[now];
}
void dfs2(LL now,LL topf)
{
idx[now]=++cnt;
a[cnt]=b[now];
top[now]=topf;
if(!son[now]) return ;
dfs2(son[now],topf);
for(LL i=head[now];i!=-1;i=edge[i].nxt)
if(!idx[edge[i].v])
dfs2(edge[i].v,edge[i].v);
}
void Build(LL k,LL ll,LL rr)
{
T[k].l=ll;T[k].r=rr;T[k].siz=rr-ll+1;
if(ll==rr)
{
T[k].w=a[ll];
return ;
}
LL mid=(ll+rr)>>1;
Build(ls,ll,mid);
Build(rs,mid+1,rr);
update(k);
}
void PointAdd(LL k,LL pos,LL val)
{
if(T[k].l==T[k].r)
{
T[k].w+=val;
return ;
}
PushDown(k);
LL mid=(T[k].l+T[k].r)>>1;
if(pos<=mid) PointAdd(ls,pos,val);
if(pos>mid) PointAdd(rs,pos,val);
update(k);
}
void IntervalAdd(LL k,LL ll,LL rr,LL val)
{
if(ll<=T[k].l&&T[k].r<=rr)
{
T[k].w+=T[k].siz*val;
T[k].f+=val;
return ;
}
PushDown(k);
LL mid=(T[k].l+T[k].r)>>1;
if(ll<=mid) IntervalAdd(ls,ll,rr,val);
if(rr>mid) IntervalAdd(rs,ll,rr,val);
update(k);
}
LL IntervalAsk(LL k,LL ll,LL rr)
{
LL ans=0;
if(ll<=T[k].l&&T[k].r<=rr)
{
ans+=T[k].w;
return ans;
}
PushDown(k);
LL mid=(T[k].l+T[k].r)>>1;
if(ll<=mid) ans+=IntervalAsk(ls,ll,rr);
if(rr>mid) ans+=IntervalAsk(rs,ll,rr);
return ans;
}
LL TreeSum(LL x,LL y)
{
LL ans=0;
while(top[x]!=top[y])//不在同一条链内
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=IntervalAsk(1,idx[top[x]],idx[x]);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
ans+=IntervalAsk(1,idx[x],idx[y]);
return ans;
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
memset(head,-1,sizeof(head));
LL N=read(),M=read();
for(LL i=1;i<=N;i++) b[i]=read();
for(LL i=1;i<=N-1;i++)
{
LL x=read(),y=read();
AddEdge(x,y);AddEdge(y,x);
}
dfs1(root,0,1);
dfs2(root,root);
Build(1,1,N);
while(M--)
{
LL opt=read(),x,val;
if(opt==1)
{
x=read(),val=read();
PointAdd(1,idx[x],val);
}
else if(opt==2)
{
x=read(),val=read();
IntervalAdd(1,idx[x],idx[x]+tot[x]-1,val);
}
else
{
x=read();
printf("%lld\n",TreeSum(root,x));
}
}
return 0;
}