QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133661 | #4941. Tree Beauty | PhantomThreshold# | WA | 252ms | 74004kb | C++20 | 2.9kb | 2023-08-02 12:34:02 | 2023-08-02 12:34:03 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int maxn = 210000;
const int maxd = 18;
int n,Q;
vector<int>E[maxn];
int dfn[maxn],dfi,dep[maxn],siz[maxn];
int fa[maxn][maxd], num[maxn][maxd];
void dfs(const int x)
{
for(int i=1;i<maxd;i++) fa[x][i]= fa[ fa[x][i-1] ][i-1];
dfn[x]=++dfi;
siz[x]=1;
num[x][0]=1;
for(auto y:E[x])
{
dep[y]=dep[x]+1;
fa[y][0]=x;
dfs(y);
siz[x]+=siz[y];
for(int d=0;d+1<maxd;d++) num[x][d+1]+=num[y][d];
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=maxd-1;i>=0;i--) if( dep[x]-dep[y]>=(1<<i) )
x=fa[x][i];
if(x==y) return x;
for(int i=maxd-1;i>=0;i--) if( fa[x][i]!=fa[y][i] )
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
struct node
{
int i,op,x,y,k;
}q[maxn]; int ans[maxn];
int t[maxn],tp;
inline bool cmp(const int x,const int y){ return dfn[x]<dfn[y]; }
vector<int>e[maxn];
vector<int>upd[maxn],query[maxn];
int ff[maxn];
int sum1[maxn];
int adDep[maxn];
void solve(const int x)
{
for(auto i:upd[x])
{
if(q[i].k==1) sum1[x]+=q[i].y;
else
{
int temp=q[i].y;
for(int d=0;temp!=0;d++)
{
adDep[dep[x]+d]+=temp;
temp/=q[i].k;
}
}
}
if(query[x].empty()==false)
{
int sum= sum1[x]*siz[x];
for(int d=0;d<maxd;d++)
sum+= adDep[dep[x]+d]*num[x][d];
for(auto i:query[x]) ans[i]+=sum;
}
for(auto y:e[x])
{
sum1[y]+=sum1[x];
solve(y);
}
for(auto i:upd[x])
{
//if(q[i].k==1) sum1[x]+=q[i].y;
//else
if(q[i].k!=1)
{
int temp=q[i].y;
for(int d=0;temp!=0;d++)
{
adDep[dep[x]+d]-=temp;
temp/=q[i].k;
}
}
}
}
void cdq(const int l,const int r)
{
if(l==r) return;
int mid=(l+r)>>1;
tp=0;
for(int i=l;i<=r;i++) t[++tp]=q[i].x;
sort(t+1,t+tp+1,cmp);
tp= unique(t+1,t+tp+1)-t-1;
for(int i=tp;i>1;i--) t[++tp]=lca(t[i],t[i-1]);
sort(t+1,t+tp+1,cmp);
tp= unique(t+1,t+tp+1)-t-1;
for(int i=1;i<=tp;i++)
{
int x=t[i];
vector<int>_,__,___;
e[x].swap(_);
upd[x].swap(__);
query[x].swap(___);
ff[x]=0;
sum1[x]=0;
}
int rt=t[1],now=rt;
for(int i=2;i<=tp;i++)
{
int y=t[i];
while( !( dfn[now]<=dfn[y] && dfn[y]<dfn[now]+siz[now] ) )
now=ff[now];
ff[y]=now;
e[now].push_back(y);
now=y;
}
for(int i=l;i<=mid;i++) if(q[i].op==1)
upd[q[i].x].push_back(i);
for(int i=mid+1;i<=r;i++) if(q[i].op==2)
query[q[i].x].push_back(i);
solve(rt);
cdq(l,mid); cdq(mid+1,r);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin>>n>>Q;
for(int i=2;i<=n;i++)
{
int p; cin>>p;
E[p].push_back(i);
}
dep[1]=1; dfs(1);
for(int i=1;i<=Q;i++)
{
q[i].i=i;
cin>>q[i].op;
if(q[i].op==1) cin>>q[i].x>>q[i].y>>q[i].k;
else cin>>q[i].x;
}
cdq(1,Q);
for(int i=1;i<=Q;i++) if(q[i].op==2)
cout<<ans[i]<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 39868kb
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: 1ms
memory: 33480kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 252ms
memory: 74004kb
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 ...
output:
0 0 0 672469600 0 1987509504 0 1681174000 0 0 3026369500 6233535100 6987949855 3856977000 14196952001 11377817000 10186774000 10394197000 9287941000 7069235348 7999042783 0 11118575600 11569594000 15377930450 5835119847 745421000 14142751700 13367272344 9835948365 2981684000 6202227015 4582682500 53...
result:
wrong answer 1st lines differ - expected: '1818724600', found: '0'