题面
Description
“奋战三星期，造台计算机”。小G响应号召，花了三小时造了台普通计算姬。普通计算姬比普通计算机要厉害一些。普通计算机能计算数列区间和，而普通计算姬能计算树中子树和。更具体地，小G的计算姬可以解决这么个问题：给定一棵n个节点的带权树，节点编号为1到n，以root为根，设sum[p]表示以点p为根的这棵子树中所有节点的权值和。计算姬支持下列两种操作:
1 给定两个整数u,v，修改点u的权值为v。
2 给定两个整数l,r，计算sum[l]+sum[l+1]+….+sum[r-1]+sum[r]
尽管计算姬可以很快完成这个问题，可是小G并不知道它的答案是否正确，你能帮助他吗？
Input
第一行两个整数n,m，表示树的节点数与操作次数。
接下来一行n个整数，第i个整数di表示点i的初始权值。
接下来n行每行两个整数ai,bi，表示一条树上的边，若ai=0则说明bi是根。
接下来m行每行三个整数，第一个整数op表示操作类型。
若op=1则接下来两个整数u,v表示将点u的权值修改为v。
若op=2则接下来两个整数l,r表示询问。
N<=10^5,M<=10^5
0<=Di,V<2^31,1<=L<=R<=N,1<=U<=N
Output
对每个操作类型2输出一行一个整数表示答案。
Sample Input
6 4
0 0 3 4 0 1
0 1
1 2
2 3
2 4
3 5
5 6
2 1 2
1 1 1
2 3 6
2 3 5
Sample Output
16
10
9
题解
子树和立马想到在$dfs$序上操作了，但是要求的答案是原来序列的一段区间……
考虑分块，零散的部分可以通过统计$dfs$序上区间和搞定
正块部分处理出来每个点对当前块的贡献次数，这个$dfs$一遍就能$O(n\sqrt n)$搞出来
具体做法就是记录每个块标号出现次数，$dfs$到$x$点时块$i$的标号出现了$k$次，说明$x$对块$i$贡献次数就是$k$了
为什么跑的这么慢呢
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
# define LL unsigned long long
using namespace std;
const int MAX=1e5+5,N=318;
struct p{
int x,y;
}c[MAX<<1];
int n,m,num,cnt,RT,k,_N;
int h[MAX],id[MAX],a[MAX],pos[MAX],bl[N],br[N],siz[MAX],tim[N];
int f[N][MAX];
LL s[MAX],Sum[N];
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num;
c[++num]=(p){h[y],x},h[y]=num;
}
void dfs(int x=RT,int fa=0)
{
id[x]=++cnt,siz[x]=1,++tim[pos[x]];
for(int i=1;i<=_N;++i)
f[i][x]+=tim[i];
for(int i=h[x];i;i=c[i].x)
if(c[i].y^fa) dfs(c[i].y,x),siz[x]+=siz[c[i].y];
--tim[pos[x]];
}
int lowbit(int x) {return x&-x;}
void change(int x,int dis)
{
for(int i=x;i<=n;i+=lowbit(i))
s[i]+=dis;
}
LL _sum(int x)
{
LL ans=0;
for(int i=x;i;i-=lowbit(i))
ans+=s[i];
return ans;
}
LL ask(int l,int r) {return _sum(r)-_sum(l-1);}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
LL Ask(int l,int r)
{
LL ans=0;
int Pl=pos[l],Pr=pos[r];
if(Pl==Pr)
{
if(bl[Pl]==l&&br[Pl]==r) return Sum[Pl];
for(int i=l;i<=r;++i)
ans+=ask(id[i],id[i]+siz[i]-1);
return ans;
}
int L=Pl+(bl[Pl]!=l),R=Pr-(br[Pr]!=r);
for(int i=L;i<=R;++i)
ans+=Sum[i];
if(L!=Pl) for(int i=l;i<=br[Pl];++i)
ans+=ask(id[i],id[i]+siz[i]-1);
if(R!=Pr) for(int i=bl[Pr];i<=r;++i)
ans+=ask(id[i],id[i]+siz[i]-1);
return ans;
}
int main()
{
k=sqrt(n=read()),m=read(),k+=(!!n%k);
for(int i=1,x;i<=n;++i)
{
a[i]=read(),pos[i]=x=(i-1)/k+1,br[x]=i;
if(pos[i]!=pos[i-1]) ++_N;
if(!bl[x]) bl[x]=i;
}
for(int i=1,x;i<=n;++i)
{
x=read();
if(!x) RT=read();
else add(x,read());
}
dfs();
for(int i=1;i<=n;++i)
{
change(id[i],a[i]);
for(int j=1;j<=_N;++j)
Sum[j]+=1ll*f[j][i]*a[i];
}
for(int i=1,op,l,r;i<=m;++i)
{
op=read(),l=read(),r=read();
if(op==1)
{
change(id[l],r-a[l]);
for(int j=1;j<=_N;++j)
Sum[j]+=1ll*f[j][l]*(r-a[l]);
a[l]=r;
}
else if(op==2) printf("%llu\n",Ask(l,r));
}
return 0;
}
