QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#274745#4941. Tree Beautyanhduc2701RE 0ms0kbC++232.9kb2023-12-03 21:05:422023-12-03 21:05:43

Judging History

你现在查看的是最新测评结果

  • [2023-12-03 21:05:43]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-12-03 21:05:42]
  • 提交

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

output:


result: