QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133998 | #4941. Tree Beauty | wtn135687 | TL | 1ms | 40404kb | C++14 | 4.4kb | 2023-08-02 20:08:34 | 2023-08-02 20:08:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e6+10,mo = 1e18+7;
int a[N];
int n,q;
vector<int>to[N];
int dfn[N],nfd[N];
int L[N],R[N];//儿子编号始终
int dep[N];
int depidR[N];
// int sz[N];//最深儿子深度
// void dfs(int u,int fa){
// sz[u]=1;
// for(int v:to[u]){
// dfs(v,u);
// sz[u]=max(sz[u],sz[v]+1);
// }
// }
void bfs(){
// for(int i=1;i<=n;i++)sort(to[i].begin(),to[i].end(),[&](int x,int y){
// return sz[x]>sz[y];
// });
queue<int>q;int cnt=0;dfn[1]=++cnt;nfd[cnt]=1;
q.push(1);dep[1]=1;depidR[1]=1;
while(q.size()){
int u=q.front();q.pop();
// cerr<<"u="<<u<<"\n";
L[u]=cnt+1;
for(int v:to[u]){
dep[v]=dep[u]+1;
dfn[v]=++cnt;nfd[cnt]=v;
depidR[dep[v]]=cnt;
q.push(v);
}
R[u]=cnt;
}
// for(int i=1;i<=n;i++)cerr<<"i="<<i<<" dfn: "<<dfn[i]<<" LR:"<<L[i]<<" "<<R[i]<<"\n";
}
inline ll q_pow(int a,int b){
ll res=1;
while(b){
if(b&1)res=res*a%mo;
a=a*a%mo;
b>>=1;
}
return res;
}
struct XDS {
struct Node{
int sum;
int t;
int len;
}seg[N<<2];
void build(int id,int l,int r){
if(l==r){seg[id].len=1;return ;}
int mid=l+r>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
seg[id].len=seg[id<<1].len+seg[id<<1|1].len;
}
void setTag(int id,int t){
seg[id].sum+=seg[id].len*t;
seg[id].t+=t;
// cerr<<"setTag: id="<<id<<" sum="<<seg[id].sum<<" t="<<t<<" len="<<seg[id].len<<"\n";
}
void pushDown(int id){
int t=seg[id].t;
seg[id<<1].sum+=seg[id<<1].len*t;seg[id<<1|1].sum+=seg[id<<1|1].len*t;
seg[id<<1].t+=t;seg[id<<1|1].t+=t;
seg[id].t=0;
}
void upDate(int id){
seg[id].sum=seg[id<<1].sum+seg[id<<1|1].sum;
// cerr<<"update id="<<id<<" sum="<<seg[id].sum<<"\n";
}
void modify(int id,int l,int r,int ql,int qr,int t){
// cerr<<"add "<<id<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<t<<"\n";
if(!(l<=ql&&qr<=r))return ;
if(l==ql&&r==qr){
setTag(id,t);return ;
}
pushDown(id);
int mid=l+r>>1;
if(qr<=mid)modify(id<<1,l,mid,ql,qr,t);
else if(ql>mid)modify(id<<1|1,mid+1,r,ql,qr,t);
else {
modify(id<<1,l,mid,ql,mid,t);modify(id<<1|1,mid+1,qr,mid+1,r,t);
}
upDate(id);
}
ll query(int id,int l,int r,int ql,int qr){
// cerr<<"query tree"<<ql<<" "<<qr<<"\n";
// cerr<<seg[id].sum<<"!\n";
if(l==qr&&r==qr)return seg[id].sum;
pushDown(id);
int mid=l+r>>1;
if(qr<=mid)return query(id<<1,l,mid,ql,qr);
else if(ql>mid)return query(id<<1|1,mid+1,r,ql,qr);
else return query(id<<1,l,mid,ql,mid)+query(id<<1|1,mid+1,r,mid+1,qr);
}
void modify(int l,int r,int y,int k,int d){//该级别的两个端点
if(l>r)return ;
if(y<q_pow(k,d))return ;
// cerr<<"modify1 l,r,y,k,d:"<<l<<" "<<r<<" "<<y<<" "<<k<<" "<<d<<"\n";
modify(1,1,n,l,r,y/(q_pow(k,d)));
// cerr<<"lr:"<<l<<" "<<r<<"\n";
// cerr<<"nfdlr = "<<nfd[l]<<" "<<nfd[r]<<"\n";
modify(L[nfd[l]],R[nfd[r]],y,k,d+1);
}
ll query(int l,int r){
if(l>r)return 0;
ll res=query(1,1,n,l,r);
// cerr<<"query res "<<l<<" "<<r<<" res= "<<res<<"\n";
res+=query(L[nfd[l]],R[nfd[r]]);
// cerr<<"query "<<l<<" "<<r<<" res= "<<res<<"\n";
return res;
}
}tree;
inline void solve(){
cin>>n>>q;
for(int i=2;i<=n;i++){int fa;cin>>fa;to[fa].push_back(i);}
// dfs(1,0);
tree.build(1,1,n);
bfs();
while(q--){
int op;cin>>op;
if(op==1){
int x,y,k;cin>>x>>y>>k;
tree.modify(dfn[x],dfn[x],y,k,0);
}
else {
int x;cin>>x;
cout<<tree.query(dfn[x],dfn[x])<<"\n";
}
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int WTN666=1;//cin>>WTN666;
while(WTN666--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 40348kb
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: 40404kb
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:
889111795 889111795 889111795 335394213 1439495113 989754057 1439495113 1378437930 1439495113 1439495113 3721395364 5586391911 3731761517 2139669372 9560374798 11466807076 7494029540 7634846710 7083792940 4463561352 6441057263 13448204463 12527513193 11208307847 13994749062 15800031108 328730661 115...