QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#274699#4941. Tree Beautyanhduc2701WA 103ms48296kbC++232.9kb2023-12-03 20:19:122023-12-03 20:19:14

Judging History

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

  • [2023-12-03 20:19:14]
  • 评测
  • 测评结果:WA
  • 用时:103ms
  • 内存:48296kb
  • [2023-12-03 20:19:12]
  • 提交

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=2e5+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());
	}
	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<=19-(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<19;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';
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 31944kb

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: 0ms
memory: 32044kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 103ms
memory: 48296kb

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...

result:

wrong answer 207th lines differ - expected: '374740858675', found: '374716539371'