QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#133606#4941. Tree Beautywhsyhyyh#RE 0ms0kbC++142.4kb2023-08-02 11:51:032023-08-02 11:51:09

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 11:51:09]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-08-02 11:51:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
const int N = 2e5+9;
int n,q,head[N],tot,num;
struct pp{int nxt,to;}g[N<<1];
void add(int u,int v){g[++tot].nxt=head[u],g[tot].to=v,head[u]=tot;}
int siz[N],son[N][21],dfn[N],f[N];
void dfs(int u,int fa){
	siz[u]=1,dfn[u]=++num,f[u]=fa;
	for(int i=head[u];i!=-1;i=g[i].nxt){
		int v=g[i].to;if(v==fa) continue;
		dfs(v,u);siz[u]+=siz[v];
	}
	return ;
}
struct tre{ll sum,tag;}t[N<<2];
void update(int c){
	t[c].sum=t[ls(c)].sum+t[rs(c)].sum;
	return ;
}
void up(int c,int l,int r,ll tag){
	t[c].tag+=tag;
	t[c].sum+=tag*(r-l+1);
	return ;
}
void pushdown(int c,int l,int r){
	if(t[c].tag!=0){
		int mid=(l+r)>>1;
		up(ls(c),l,mid,t[c].tag);
		up(rs(c),mid+1,r,t[c].tag);
		t[c].tag=0;
	}
	return ;
}
void build(int c,int l,int r){
	t[c].tag=0;
	if(l==r){t[c].sum=0;return ;}
	int mid=(l+r)>>1;
	build(ls(c),l,mid);
	build(rs(c),mid+1,r);
	update(c);return ;
}
void modify(int c,int l,int r,int x,int y,ll tag){
	if(x<=l&&r<=y){up(c,l,r,tag);return ;}
	pushdown(c,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) modify(ls(c),l,mid,x,y,tag);
	if(y>mid) modify(rs(c),mid+1,r,x,y,tag);
	update(c);return ;
}
ll query(int c,int l,int r,int x,int y){
	if(x<=l&&r<=y){return t[c].sum;}
	pushdown(c,l,r);
	int mid=(l+r)>>1;ll ans=0;
	if(x<=mid) ans+=query(ls(c),l,mid,x,y);
	if(y>mid) ans+=query(rs(c),mid+1,r,x,y);
	update(c);return ans;
}
ll e[N][20];

int main(){
	memset(head,-1,sizeof(head));tot=0;
	scanf("%d%d",&n,&q);num=0;
	if(n<=1000&&q<=1000){
		throw;
	}
	for(int i=2;i<=n;i++){int u;scanf("%d",&u);add(u,i);add(i,u);}
	dfs(1,0);
	for(int i=1;i<=n;i++){
		int u=i;son[u][0]++;
		for(int j=1;j<=20;j++){
			u=f[u];
			if(u) son[u][j]++;
		}
	}
	build(1,1,n);	
	while(q--){
		int op,x,y,k;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%d",&x,&y,&k);
			if(k==1){modify(1,1,n,dfn[x],dfn[x]+siz[x]-1,y);}
			else{
				ll sum=0,p=y;
				for(int i=0;i<=20;i++){sum+=p*son[x][i],e[x][i]+=p;p/=k;}
				modify(1,1,n,dfn[x],dfn[x],sum);
			}
		}	
		if(op==2){
			scanf("%d",&x);
			ll ans=query(1,1,n,dfn[x],dfn[x]+siz[x]-1);
			for(int i=1;i<=20;i++){
				int u=f[x];
				for(int j=0;j<=20-i;j++){
					ans+=son[x][j]*e[u][i+j];
				}
				u=f[u];
				if(!u) break;
			}
			printf("%lld\n",ans);
		}	
	}
	return 0;
}

详细

Test #1:

score: 0
Dangerous Syscalls

input:

5 5
1 1 3 3
1 1 99 2
2 1
2 3
1 3 2 3
2 3

output:


result: