QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133917 | #4941. Tree Beauty | PlentyOfPenalty | RE | 2ms | 10412kb | C++14 | 2.6kb | 2023-08-02 17:29:29 | 2023-08-02 17:29:31 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned un;
ll read()
{
ll x=0;char c=getchar();
bool f=0;
while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f?-x:x;
}
const int MAXN = 100011,L = 18;
std::vector<int>g[MAXN];
int dfn[MAXN],ed[MAXN], fa[MAXN],cur;
void dfs(int u)
{
dfn[u]=++cur;
for(auto v:g[u])dfs(v);
ed[u]=cur;
}
int n,q;
struct Segment_Tree
{
struct node
{
ll sum,tag;
void pushtag(ll k,ll len)
{
sum+=k*len,tag+=k;
}
}t[MAXN];
#define rt t[num]
#define tl t[num<<1]
#define tr t[num<<1|1]
void pushdown(un l,un r,un num)
{
if(!rt.tag)return;
un mid=(l+r)>>1;
tl.pushtag(rt.tag,mid-l+1);
tr.pushtag(rt.tag,r-mid);
rt.tag=0;
}
void Add(un ql,un qr,ll k,un l=1,un r=n,un num=1)
{
if(ql<=l&&r<=qr)return rt.pushtag(k,r-l+1);
pushdown(l,r,num);
un mid=(l+r)>>1;
if(ql<=mid)Add(ql,qr,k,l,mid,num<<1);
if(qr>mid)Add(ql,qr,k,mid+1,r,num<<1|1);
rt.sum=tl.sum+tr.sum;
}
ll Qsum(un ql,un qr,un l=1,un r=n,un num=1)
{
if(ql<=l&&r<=qr)return rt.sum;
pushdown(l,r,num);
ll res=0;
un mid=(l+r)>>1;
if(ql<=mid)res+=Qsum(ql,qr,l,mid,num<<1);
if(qr>mid)res+=Qsum(ql,qr,mid+1,r,num<<1|1);
return res;
}
}sgt;
int cnt[MAXN][L];
ll ctrb[MAXN][L];
int main()
{
n=read(),q=read();
for(int i=2;i<=n;++i)fa[i]=read(),g[fa[i]].emplace_back(i);
dfs(1);
for(int u=1;u<=n;++u)
{
int p=u;
for(int i=0;i<L&&p;++i,p=fa[p])
++cnt[p][i];
}
while(q--)
{
int op=read(),x=read();
if(op==1)
{
int y=read(),k=read();
if(k==1)sgt.Add(dfn[x],ed[x],y);
else
{
ll tot=0;
for(int i=0;i<L;++i)
ctrb[x][i]+=y,tot+=ll(cnt[x][i])*y,y/=k;
sgt.Add(dfn[x],dfn[x],tot);
}
}
else
{
ll ans=sgt.Qsum(dfn[x],ed[x]);
//printf("query x=%d,ans=%lld\n",x,ans);
int p=fa[x];
for(int i=0;i<L&&p;++i,p=fa[p])
{
//printf("p=%d,i=%d\n",p,i);
for(int j=i+1;j<L;++j)
ans+=ctrb[p][j]*cnt[x][j-i-1];
//printf("new ans = %lld\n",ans);
}
printf("%lld\n",ans);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10412kb
input:
5 5 1 1 3 3 1 1 99 2 2 1 2 3 1 3 2 3 2 3
output:
245 97 99
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 10404kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Runtime Error
input:
100000 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...