样例全对,提交全错,求调
查看原帖
样例全对,提交全错,求调
1059455
ybw0731楼主2025/6/13 14:57
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int f=1,x=0;
	char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<1)+(x<<3)+(s^48);
		s=getchar();
	}
	return x*f;
}
const int N=5e5+5;
int n,m;
vector<int>mp[N];
int fa[N],dep[N],siz[N],son[N];
void Dfs(int u){
	dep[u]=dep[fa[u]]+1;
	siz[u]=1;
	int mx=0;
	for(int v:mp[u]){
		Dfs(v);
		siz[u]+=siz[v];
		if(siz[v]>mx){
			son[u]=v;
			mx=siz[v];
		}
	}
}
int tot;
int dfn[N],top[N];
void Dfs(int u,int tp){
	top[u]=tp;
	dfn[u]=++tot;
	if(!son[u]) return;
	Dfs(son[u],tp);
	for(int v:mp[u]){
		if(v==son[u]) continue;
		Dfs(v,v);
	}
}
int tr[N<<2],lz[N<<2];
void Update(int rt,int l,int r,int pos,int val){
	if(l==r){
		tr[rt]+=val;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid) Update(rt<<1,l,mid,pos,val);
	else Update(rt<<1|1,mid+1,r,pos,val);
	tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}
int Query(int rt,int l,int r,int x,int y){
	if(x<=l&&r<=y) return tr[rt];
	int mid=l+r>>1,ans=0;
	if(x<=mid) ans=Query(rt<<1,l,mid,x,y);
	if(y>mid) ans+=Query(rt<<1|1,mid+1,r,x,y);
	return ans;
}
int Query(int u,int v){
	int ans=0;
	while(top[u]-top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ans+=Query(1,1,n,dfn[top[u]],dfn[v]);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	ans+=Query(1,1,n,dfn[u],dfn[v]);
	return ans;
}
int a[N];
signed main(){
	n=read(); m=read();
	a[1]=read();
	for(int i=2;i<=n;i++){
		a[i]=read();
		fa[i]=read();
		mp[fa[i]].push_back(i);
	}
	Dfs(1);
	Dfs(1,1);
	while(m--){
		char op; cin>>op;
		int x=read();
		if(op=='p'){
			int y=read();
			Update(1,1,n,dfn[x],y);
		} 
		else{
			if(x==1) cout<<a[x]<<endl;
			else cout<<a[x]+Query(1,fa[x])<<endl;
		} 
	}
	return 0;
}
2025/6/13 14:57
加载中...