萌新刚学oi 树状数组爆0求助
查看原帖
萌新刚学oi 树状数组爆0求助
638537
g1ove楼主2023/7/17 20:59

rt,不知道咋就炸了

#include<bits/stdc++.h>
#define MAXN 300005
#define ll long long
using namespace std;
ll mod=1000000007;
int n,m;
ll dep[MAXN];
int in[MAXN],out[MAXN],id;
int head[MAXN],tot=1;
ll tr[3][MAXN];
struct edge{
	int to,next;
}e[MAXN];
void insert(int u,int v)
{
	e[tot]=(edge){v,head[u]};
	head[u]=tot++;
}
void add(int p,int x,ll v)
{
	while(x<=n)
	{
		tr[p][x]=(tr[p][x]+v%mod+mod)%mod;
		x+=x&-x;
	}
}
ll ask(int p,int x)
{
	ll sum=0;
	while(x)
	{
		sum=(tr[p][x]+sum+mod)%mod;
		sum%=mod;
		x-=x&-x;
	}
	return sum;
}
void updata(int p,int l,int r,ll v)
{
	add(p,l,v);
	add(p,r+1,-v);
}
void dfs(int now,int fa)
{
	dep[now]=dep[fa]+1;
	in[now]=++id;
	for(int i=head[now];i;i=e[i].next)
	{
		int son=e[i].to;
		dfs(son,now);
	}
	out[now]=id;
}
int main()
{
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		insert(x,i);
	}
	scanf("%d",&m); 
	dfs(1,0);
	for(int i=1;i<=m;i++)
	{
		int opr,u;
		ll x,k;
		scanf("%d%d",&opr,&u);
		if(opr==1)
		{
			scanf("%lld%lld",&x,&k);
			updata(0,in[u],out[u],(x+k*dep[u]%mod)%mod);
			updata(1,in[u],out[u],k);
		}
		else
			printf("%lld\n",(ask(0,u)-dep[u]*ask(1,u)%mod+2*mod)%mod);
	}
	return 0;
}
/*
v[now]=val-k*(dep[now]-dep[root])
=val-k*dep[now]+k*dep[root]
其中k,val,dep为已知
val-k*dep[root] 一棵树搞了
维护一个k和就ok

两个树状数组:
V值
and K值 
*/
2023/7/17 20:59
加载中...