QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133759 | #4941. Tree Beauty | Vengeful_Spirit# | TL | 2ms | 26008kb | C++20 | 4.4kb | 2023-08-02 13:54:35 | 2023-08-02 13:54:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int sz[N],dep[N],dfn[N],son[N],fa[N],top[N];
int n, a[N];
vector<int> e[N];
void dfs(int x,int f){
dep[x]=dep[f]+1;
for(auto v:e[x]){
dfs(v,x);
sz[x]+=sz[v];
if(sz[v]>sz[son[x]])son[x]=v;
}
}
int indec;
int dfnr[N];
void dfs2(int x,int tp){
top[x]=tp;
dfn[x]=++indec;
if(son[x]){
dfs2(son[x],tp);
}
for(auto v:e[x]){
if(v!=son[x]){
dfs2(v,v);
}
}
dfnr[x]=indec;
}
long long tag[18][N<<2];
void modify(int step,int x,int l,int r,int L,int R,int v){
if(l==L&&r==R){
tag[step][x]+=v;
return;
}
else{
int mid=(l+r)/2;
if(R<=mid){
modify(step,x<<1,l,mid,L,R,v);
}
else if(L>mid){
modify(step,x<<1|1,mid+1,r,L,R,v);
} else {
modify(step,x<<1,l,mid,L,mid,v);
modify(step,x<<1|1,mid+1,r,mid+1,R,v);
}
}
}
long long query(int step,int x,int l,int r,int pos){
if(l==r){return tag[step][x];}
else {
int mid=(l+r)/2;
if(pos<=mid) return tag[step][x]+query(step,x<<1,l,mid,pos);
else return tag[step][x]+query(step,x<<1|1,mid+1,r,pos);
}
}
// void modify(int x,int v){
// while(x){
// modify(1,1,n,dfn[top[x]],dfn[x],v);
// x=fa[top[x]];
// }
// }
int bfn[N];
int sonl[N],sonr[N];
void bfs(){
deque<pair<int,int>>q;
q.push_back({1,1});
int inded=0;
while(!q.empty()){
auto [x,d]=q.front();
bfn[x]=++inded;
q.pop_front();
for(auto v:e[x]){
q.push_back({v,d+1});
}
}
}
void DFS(int x){
sonl[bfn[x]]=n+1;
sonr[bfn[x]]=-1;
for(auto y:e[x]){
DFS(y);
sonl[bfn[x]]=min(sonl[bfn[x]],bfn[y]);
sonr[bfn[x]]=max(sonr[bfn[x]],bfn[y]);
}
}
void add(int l,int r,int num,int k){
for(int step=0;num;num/=k,++step){
modify(step,1,1,n,l,r,num);
}
}
// 2nd segtree
int t[N<<2],tg[N<<2];
void pushdown(int x){
t[x<<1]+=tg[x];t[x<<1|1]+=tg[x];
tg[x<<1]+=tg[x];tg[x<<1|1]+=tg[x];
tg[x]=0;
}
void MODIFY(int x,int l,int r,int L,int R,int v){
if(l==L&&r==R){
t[x]+=v;
tg[x]+=v;
return;
}
else{
pushdown(x);
int mid=(l+r)/2;
if(R<=mid){
MODIFY(x<<1,l,mid,L,R,v);
}
else if(L>mid){
MODIFY(x<<1|1,mid+1,r,L,R,v);
} else {
MODIFY(x<<1,l,mid,L,mid,v);
MODIFY(x<<1|1,mid+1,r,mid+1,R,v);
}
}
}
long long QUERY(int x,int l,int r,int L, int R){
if(l==r){return t[x];}
else {
pushdown(x);
int mid=(l+r)/2;
if(R<=mid) return QUERY(x<<1,l,mid,L,R);
else if(L>mid) return QUERY(x<<1|1,mid+1,r,L,R);
return QUERY(x<<1,l,mid,L,mid)+QUERY(x<<1|1,mid+1,r,mid+1,R);
}
}
// void upd(int x,long long v){
// while(x){
// // cerr<<x<<" "<<top[x]<<endl;
// MODIFY(1,1,n,dfn[top[x]],dfn[x],v);
// x=fa[top[x]];
// }
// }
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
// 1 X Y K
// 2 X
cin >> n;
int q;
cin >> q;
for(int i = 2; i <= n; ++i) {
cin >> fa[i];
e[fa[i]].push_back(i);
}
dfs(1, 0);
dfs2(1, 1);
bfs();
DFS(1);
for(int i=2;i<=n;++i)sonr[i]=max(sonr[i],sonr[i-1]);
for(int i=n-1;i;--i)sonl[i]=min(sonl[i],sonl[i+1]);
// for(int i=1;i<=n;++i)cerr<<i<<" "<<bfn[i]<<" "<<sonl[i]<<" "<<sonr[i]<<endl;
for(int i = 1; i <= q; ++i) {
int opt;
cin >> opt;
if(opt == 1) {
int x, y, k;
cin >> x >> y >> k;
if(k==1) {
MODIFY(1,1,n,dfn[x],dfnr[x],y);
} else {
int l = bfn[x], r = bfn[x];
l = sonl[l];
r = sonr[r];
long long all=0;
all=y;
y/=k;
// cerr<<"!!!"<<endl;
while(y) {
// cerr<<l<<" "<<r<<" "<<y<<" "<<k<<endl;
add(l,r,y,k);
all+=(r-l+1)*1ll*y;
y/=k;
l=sonl[l];
r=sonr[r];
if(l>r)break;
}
// cerr<<"!"<<endl;
if(x) MODIFY(1,1,n,dfn[x],dfn[x],all);
// cerr<<dfn[x]<<" "<<all<<endl;
// upd(x, all);
// if(fa[x]) upd(fa[x],all);
}
} else {
int x;
cin >> x;
// cerr<<dfn[x]<< " "<<dfnr[x] << " ssss"<<endl;
long long ans=QUERY(1,1,n,dfn[x],dfnr[x]);
// cerr << "ans = " << ans << endl;
int l=bfn[x],r=bfn[x];
for(int i=0;i<18;++i){
ans+=query(i,1,1,n,bfn[x])*(r-l+1);
l=sonl[l];
r=sonr[r];
if(l>r)break;
}
cout<<ans<<"\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 26008kb
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: 11708kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Time Limit Exceeded
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:
1818724600 1818724600 1818724600 672469600 2920352548 1987509504 2920352548 2782801948 2920352548 2920352548 7518672977 11295020015 7543062544 4383229800 19258702398 22947288874 15221147536 15428570536 14322314536 9119623396 12969783379 26872020588 25039643385 22398749036 27923029652 31534374661 745...