QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134025 | #4941. Tree Beauty | wtn135687 | WA | 94ms | 79364kb | C++14 | 5.2kb | 2023-08-02 20:44:00 | 2023-08-02 20:44:03 |
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;
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;
}
int a[N];
int n,q;
vector<int>to[N];
int dfn[N],nfd[N],R[N];
// int L[N],R[N];//儿子编号始终
int dep[N];
int fa[N];
int add[21][N];//给下面每层深度的儿子的加
int num[21][N];//每层深度的儿子的数量
// void bfs(){
// 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;
// }
// }
void dfs(int u,int fat){
fa[u]=fat;
static int cnt;
dfn[u]=++cnt;
for(int v:to[u]){
dfs(v,u);
}R[u]=cnt;
num[0][u]=1;
for(int i=1;i<=20;i++){
for(int v:to[u])num[i][u]+=num[i-1][v];
}
}
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;
// }
void modify(int x,int y,int k){
if(k==1){modify(1,1,n,dfn[x],R[x],y);return ;}
int sum=0;
for(int i=0;i<=20;i++){
if(y<q_pow(k,i))break;
add[i][x]+=(y/q_pow(k,i));
sum+=num[i][x]*(y/q_pow(k,i));
}
modify(1,1,n,dfn[x],dfn[x],sum);
}
ll query(int x){
int res=query(1,1,n,dfn[x],dfn[x]);
for(int i = 1, now = fa[x]; i <= 20 && now; i ++, now = fa[now]){
for(int j = i; j <= 20 ; j ++){
res += add[j][now] * num[j - i][x];
// cerr << res << ' ' << f[now][j] << ' ' << num[x][j - 1] << '\n';
}
}
// for(int i=1;i<=20;i++){
// x=fa[x];if(!x)break;
// res+=num[i][x]*add[i][x];
// }
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);}
tree.build(1,1,n);
// bfs();
dfs(1,0);
while(q--){
int op;cin>>op;
if(op==1){
int x,y,k;cin>>x>>y>>k;
tree.modify(x,y,k);
}
else {
int x;cin>>x;
cout<<tree.query(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: 3ms
memory: 52664kb
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: 6ms
memory: 36240kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 94ms
memory: 79364kb
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 76417 0 129963 0 76417 0 0 78607 78607 468817 453762 230471 144023 230470 230470 230470 22826477 11376799 0 144023 230470 5811920 78063 745421 305459 242814 474024 745421 13938831 833215 833215 1072013 476935 833215 493756 230507 7366190 393253 0 256058 750988 528845 393254 232881 1172104 2846...
result:
wrong answer 1st lines differ - expected: '1818724600', found: '0'