QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#133769 | #4941. Tree Beauty | nameless_story# | RE | 3ms | 30156kb | C++17 | 3.6kb | 2023-08-02 13:57:54 | 2023-08-02 13:57:55 |
Judging History
answer
#pragma GCC optimize(2)
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
const int N=200005;
int n,m;
int dfn[N],trid[N],maxd[N],ind,hson[N],som[N],deep[N],dad[N];
int dnum[N];
vector<int> V[N],num[N],nom[N],fum[N];
void dfs1(int u,int fa)
{
deep[u]=deep[fa]+1;
dnum[deep[u]]++;
som[u]=1;
dad[u]=fa;
for(int v:V[u])
{
if(v==fa)
continue;
dfs1(v,u);
som[u]=som[v]+1;
if(maxd[v]+1>maxd[u])
maxd[u]=maxd[v]+1,hson[u]=v;
}
}
void dfs2(int u,int fa)
{
dfn[u]=++ind;
trid[ind]=u;
if(!hson[u])
{
num[u].pb(1);
for(int i=1;i<=20&&i<=num[u].size();i++)
nom[u].pb(num[u][num[u].size()-i]),fum[u].pb(0);
return;
}
dfs2(hson[u],u);
num[u].swap(num[hson[u]]);
num[u].pb(1);
for(int v:V[u])
{
if(v==fa||v==hson[u])
continue;
dfs2(v,u);
assert(num[v].size()<num[u].size());
for(int i=1;i<=num[v].size();i++)
num[u][num[u].size()-1-i]+=num[v][num[v].size()-i];
}
for(int i=1;i<=20&&i<=num[u].size();i++)
nom[u].pb(num[u][num[u].size()-i]),fum[u].pb(0);
}
struct node
{
ll v,lazy;
}tree[N<<2];
#define lc pos<<1
#define rc pos<<1|1
void frog(int pos,int l,int r,ll k)
{
tree[pos].v+=k*(r-l+1);
tree[pos].lazy+=k;
}
void pushdown(int pos,int l,int r)
{
int mid=l+r>>1;
frog(lc,l,mid,tree[pos].lazy);
frog(rc,mid+1,r,tree[pos].lazy);
tree[pos].lazy=0;
}
void modify(int pos,int l,int r,int nl,int nr,ll k)
{
assert(nl<=nl&&nl>=1&&nr<=n);
if(l>=nl&&r<=nr)
{
tree[pos].v+=k*(r-l+1);
tree[pos].lazy+=k;
return;
}
int mid=l+r>>1;
pushdown(pos,l,r);
if(nl<=mid)
modify(lc,l,mid,nl,nr,k);
if(nr>mid)
modify(rc,mid+1,r,nl,nr,k);
tree[pos].v=tree[lc].v+tree[rc].v;
}
ll seek(int pos,int l,int r,int nl,int nr)
{
if(l>=nl&&r<=nr)
{
return tree[pos].v;
}
int mid=l+r>>1;
ll ret=0;
pushdown(pos,l,r);
if(nl<=mid)
ret+=seek(lc,l,mid,nl,nr);
if(nr>mid)
ret+=seek(rc,mid+1,r,nl,nr);
return ret;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
for(int i=2;i<=n;i++)
{
int p;
cin>>p;
V[p].pb(i);
}
dfs1(1,0);
dfs2(1,0);
// for(int i=1;i<=n;i++)
// cerr<<num[i].size()<<'\n';
while(m--)
{
int opt;
cin>>opt;
if(opt==1)
{
int x,y,K;
cin>>x>>y>>K;
if(K==1)
{
modify(1,1,n,dfn[x],dfn[x]+som[x]-1,y);
}
else
{
ll ret=0;
for(int i=0;i<nom[x].size();i++)
{
ret+=nom[x][i]*1ll*y;
fum[x][i]+=y;
y/=K;
}
modify(1,1,n,dfn[x],dfn[x],ret);
}
}
else
{
int x;
cin>>x;
ll out=0;
out=seek(1,1,n,dfn[x],dfn[x]+som[x]-1);
vector fume(nom[x].size(),0);
for(int i=1,up=dad[x];i<=20&&up;i++,up=dad[up])
{
for(int j=i;j<nom[up].size();j++)
assert(j-i<fume.size()),fume[j-i]+=fum[up][j];
}
for(int i=0;i<nom[x].size();i++)
out+=nom[x][i]*1ll*fume[i];
cout<<out<<'\n';
}
}
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 30156kb
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: 26032kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Dangerous Syscalls
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 ...