QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#274745 | #4941. Tree Beauty | anhduc2701 | RE | 0ms | 0kb | C++23 | 2.9kb | 2023-12-03 21:05:42 | 2023-12-03 21:05:43 |
answer
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define int long long
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
int n,q;
vector<int>G[maxn];
int p[maxn];
struct segtree{
int N;
vector<ll>st;
vector<ll>lazy;
void init(int _n){
N=_n;
st.assign(4*N+5,0);
lazy.assign(4*N+5,0);
}
void push(int id,int l,int mid,int r){
if(lazy[id]){
st[id*2]+=lazy[id]*(mid-l+1);
st[id*2+1]+=lazy[id]*(r-mid);
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
lazy[id]=0;
}
}
void update(int id,int l,int r,int u,int v,ll val){
if(r<u || v<l)return;
if(u<=l && r<=v){
st[id]+=val*(r-l+1);
lazy[id]+=val;
return;
}
int mid=(l+r)/2;
push(id,l,mid,r);
update(id*2,l,mid,u,v,val);
update(id*2+1,mid+1,r,u,v,val);
st[id]=st[id*2]+st[id*2+1];
}
ll get(int id,int l,int r,int u,int v){
if(r<u || v<l)return 0;
if(u<=l && r<=v){
return st[id];
}
int mid=(l+r)/2;
push(id,l,mid,r);
return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
}
void upd(int l,int r,ll val){
if(l<=r){
update(1,1,N,l,r,val);
}
}
ll get(int l,int r){
if(l>r)return 0;
return get(1,1,N,l,r);
}
}A[maxn],B;
int tin[maxn];
int eu[maxn];
int tout[maxn];
int h[maxn];
int ma=0;
int s=0;
vector<int>D[maxn];
void dfs(int u){
tin[u]=++s;
eu[s]=u;
ma=max(ma,h[u]);
D[h[u]].pb(tin[u]);
for(auto v:G[u]){
h[v]=h[u]+1;
dfs(v);
}
tout[u]=s;
}
ll value[maxn];
signed main(){
freopen("input.inp","r",stdin);
freopen("output.out","w",stdout);
cin.tie(0),cout.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for(int i=2;i<=n;i++){
cin >> p[i];
G[p[i]].pb(i);
}
dfs(1);
for(int i=0;i<=ma;i++){
A[i].init(D[i].size());
}
// cout << ma << '\n';
B.init(n);
for(int ti=1;ti<=q;ti++){
int type;
cin >> type;
if(type==1){
int x,y,k;
cin >> x >> y >> k;
if(k==1){
B.upd(tin[x],tout[x],y);
}
else{
int d=1;
int he=h[x];
ll ans=0;
vector<ll>con;
while(y/d>0){
int l=lower_bound(D[he].begin(),D[he].end(),tin[x])-D[he].begin()+1;
int r=upper_bound(D[he].begin(),D[he].end(),tout[x])-D[he].begin();
A[he].upd(l,r,y/d);
con.pb((r-l+1)*(y/d));
d*=k;
he++;
}
for(int i=1;i<=335-(int)con.size();i++){
x=p[x];
}
while(p[x]!=0 && con.size()){
ans+=con.back();
con.pop_back();
x=p[x];
value[x]+=ans;
}
if(p[x]!=1){
B.upd(tin[p[x]],tin[p[x]],ans);
}
}
}
else{
int x;
cin >> x;
int he=h[x];
ll ans=0;
for(int i=0;i<335;i++){
int l=lower_bound(D[he].begin(),D[he].end(),tin[x])-D[he].begin()+1;
int r=upper_bound(D[he].begin(),D[he].end(),tout[x])-D[he].begin();
ans+=A[he].get(l,r);
he++;
}
ans+=B.get(tin[x],tout[x]);
cout << ans+value[x] << '\n';
}
}
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
5 5 1 1 3 3 1 1 99 2 2 1 2 3 1 3 2 3 2 3