QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#134043 | #4941. Tree Beauty | wtn135687 | TL | 4ms | 18604kb | C++14 | 6.3kb | 2023-08-02 21:02:09 | 2023-08-02 21:02:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e5+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 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);
}
// int seg[N << 2], tag[N << 2];
// void settag(int id, int l, int r, int t){
// seg[id] += t * (r - l + 1);
// tag[id] += t;
// }
// void down(int id, int l, int r){
// if(tag[id] == 0) return;
// int mid = (l + r) >> 1;
// settag(id << 1, l, mid, tag[id]);
// settag(id << 1 | 1, mid + 1, r, tag[id]);
// tag[id] = 0;
// }
// void modify(int id, int l, int r, int ql, int qr, int val){
// if(ql == l && qr == r){
// settag(id, l, r, val);
// return ;
// }
// int mid = (l + r) >> 1;
// down(id, l, r);
// if(qr <= mid){
// modify(id << 1, l, mid, ql, qr, val);
// }else if(ql > mid){
// modify(id << 1 | 1, mid + 1, r, ql, qr, val);
// }else{
// modify(id << 1, l, mid, ql, mid, val);
// modify(id << 1 | 1, mid + 1, r, mid + 1, qr, val);
// }
// seg[id] = seg[id << 1] + seg[id << 1 | 1];
// }
// int query(int id, int l, int r, int ql, int qr){
// if(ql == l && qr == r) return seg[id];
// int mid = (l + r) >> 1;
// down(id, l, r);
// 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 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);
// }
void modify(int x, int y, int k){
if(k == 1) {
modify(1, 1, n, dfn[x], R[x], y);
return;
}
int sum = 0;
add[0][x] += y;
sum = y;
for(int i = 1, val = y / k; i <= 20 && val; i ++, val /= k){
add[i][x] += val;
sum += val * num[i][x];
}
// cout << sum << "qaq\n";
modify(1, 1, n, dfn[x], dfn[x], sum);
}
ll query(int x){
int res=query(1,1,n,dfn[x],R[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);}
dfs(1,0);
tree.build(1,1,n);
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();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 18604kb
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: 3ms
memory: 13636kb
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:
961784362 961784362 961784362 399890161 1561470840 1070029073 1561470840 1491090783 1561470840 1561470840 4008642299 6001610752 4116799060 2611836330 10154679645 11957629292 7978400503 8079576833 7526909773 4974655507 7000163844 14096916697 13141915972 11853433020 14563731496 16507001993 666406374 1...