建议先完成前缀题目顶点加路径和

思路

和前缀题目很像，先把树拆成一个个的链，再通过性质求和。注意到一个子树内的所有节点的dfs序一定连续（访问完一个子树才会访问下一个），我们只需在线段树上找到这个子树所代表的区间，进行求和计算即可。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
vector<int>G[N];
int dep[N],fa[N],son[N],siz[N],top[N],dfn[N],_dfn[N],tsp;
void dfs1(int x,int xfa)//预处理 
{
	dep[x]=dep[xfa]+1;fa[x]=xfa;siz[x]=1;son[x]=-1;
	for(int i:G[x])if(i!=xfa)
	{
		dfs1(i,x);
		siz[x]+=siz[i];
		if(son[x]==-1||siz[son[x]]<siz[i])son[x]=i;
	}
}
void dfs2(int x,int tp)//记录dfs序 
{
	top[x]=tp;dfn[x]=++tsp;_dfn[tsp]=x;
	if(son[x]!=-1)dfs2(son[x],tp);
	for(int i:G[x])if(i!=fa[x]&&i!=son[x])dfs2(i,i);
}
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
struct node{int l,r,s;}tr[N<<2];int a[N];
void pu(int p){tr[p].s=tr[lc(p)].s+tr[rc(p)].s;}
void build(int p,int l,int r)//建线段树 
{
	tr[p]={l,r,0};
	if(l==r){tr[p].s=a[_dfn[l]];return ;}
	int mid=(l+r)>>1;
	build(lc(p),l,mid),build(rc(p),mid+1,r);
	pu(p);
}
void change(int p,int x,int k)//将x的值修改为k 
{
	if(tr[p].r<x||x<tr[p].l)return ;
	if(tr[p].l==tr[p].r){tr[p].s+=k;return ;}
	change(lc(p),x,k);change(rc(p),x,k);
	pu(p);
}
int query(int p,int l,int r)//询问l到r之间的和 
{
	if(tr[p].r<l||r<tr[p].l)return 0;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].s;
	return query(lc(p),l,r)+query(rc(p),l,r);
}
signed main()
{
	int n,q;scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=2;i<=n;i++)
	{
		int x;scanf("%lld",&x);x++;//我习惯从1开始计算 
		G[i].push_back(x);
	}
	dfs1(1,0);dfs2(1,1);
	build(1,1,n);
	while(q--)
	{
		int op,x,y;scanf("%lld%lld",&op,&x);x++;
		if(op==0)
		{
			scanf("%lld",&y);y++;
			change(1,dfn[x],y-1);
		}
		else printf("%lld\n",query(1,dfn[x],dfn[x]+siz[x]-1));
		//dfn[x]为该子树根节点，dfn[x]+siz[x]-1为该子树最后一个节点（子树大小为siz[x]） 
	}
	return 0;//完结撒花 
}

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
#define int long long
vector<int>G[N];
int dep[N],fa[N],son[N],siz[N],top[N],dfn[N],_dfn[N],tsp;
void dfs1(int x,int f)
{
	dep[x]=dep[f]+1;fa[x]=f;siz[x]=1;int mx=0;
	for(int y:G[x])if(y!=f)
	{
		dfs1(y,x);
		siz[x]+=siz[y];
		if(mx<siz[y])mx=siz[y],son[x]=y;
	}
}
void dfs2(int x,int tp)
{
	top[x]=tp;dfn[x]=++tsp;_dfn[tsp]=x;
	if(son[x])dfs2(son[x],tp);
	for(int y:G[x])if(y!=fa[x]&&y!=son[x])dfs2(y,y);
}
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
struct node{int l,r,s;}tr[N<<2];int a[N];
void pushup(int p){tr[p].s=tr[lc(p)].s+tr[rc(p)].s;}
void bt(int p,int l,int r)
{
	tr[p]={l,r,0};
	if(l==r){tr[p].s=a[_dfn[l]];return;}
	int mid=(l+r)>>1;
	bt(lc(p),l,mid),bt(rc(p),mid+1,r);
	pushup(p);
}
void change(int p,int x,int k)
{
	if(tr[p].r<x||tr[p].l>x)return;
	if(tr[p].l==tr[p].r)
	{
		tr[p].s+=k;
		return ;
	}
	change(lc(p),x,k);change(rc(p),x,k);
	pushup(p);
}
int query(int p,int l,int r)
{
	if(tr[p].r<l||tr[p].l>r)return 0;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].s;
	return query(lc(p),l,r)+query(rc(p),l,r);
}
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=2;i<=n;i++)
	{
		int x;cin>>x;x++;
		G[x].push_back(i);
	}
	dfs1(1,0);dfs2(1,1);
	bt(1,1,n);
	while(q--)
	{
		int op,x,y;cin>>op;
		if(op==0)
		{
			cin>>x>>y;x++;
			change(1,dfn[x],y);
		}
		else
		{
			cin>>x;x++;
			cout<<query(1,dfn[x],dfn[x]+siz[x]-1)<<'\n';
		}
	}
	return 0;
}