QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#134051 | #4941. Tree Beauty | wtn135687 | TL | 3ms | 19948kb | C++14 | 5.9kb | 2023-08-02 21:16:53 | 2023-08-02 21:16:55 |
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];
inline void setTag(int id,int t,int l,int r){
int len=r-l+1;
seg[id].sum+=len*t;
seg[id].t+=t;
}
inline void pushDown(int id,int l,int r){
int t=seg[id].t;
if(!t)return;
int mid=l+r>>1;
setTag(id<<1,t,l,mid);setTag(id<<1|1,t,mid+1,r);
seg[id].t=0;
}
inline void upDate(int id){
seg[id].sum=seg[id<<1].sum+seg[id<<1|1].sum;
}
// void modify(int id,int l,int r,int ql,int qr,int t){
// assert(l<=ql&&qr<=r);
// // if(!(l<=ql&&qr<=r)){
// // }
// if(l==ql&&r==qr){setTag(id,t,l,r);return ;}
// pushDown(id,l,r);
// 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){
if(l==qr&&r==qr)return seg[id].sum;
pushDown(id,l,r);
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, val,l, r);
return ;
}
int mid = (l + r) >> 1;
pushDown(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].sum = seg[id << 1].sum + seg[id << 1 | 1].sum;
}
// 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: 0ms
memory: 19948kb
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: 12868kb
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...