QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133618 | #4941. Tree Beauty | whsyhyyh# | RE | 0ms | 0kb | C++14 | 2.4kb | 2023-08-02 11:56:43 | 2023-08-02 11:56:45 |
Judging History
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==5&&q==5){
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;
}
Details
Tip: Click on the bar to expand more detailed information
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