样例全过,一测全错,求调
查看原帖
样例全过,一测全错,求调
1259667
lizhixin20090311楼主2024/12/21 22:18
#include<iostream>    
#include<cstdio>  
#include<cmath>   
using namespace std;  
inline int read()  
{
    register int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)) 
	{
		if(c=='-') f=-1;
		c=getchar();
	}
    while(isdigit(c)) x=x*10+c-48,c=getchar();
    return x*f;   
}

const int N=500011;
int n,m;
int a[N];
struct edge
{
	int to,next;
}e[N<<1];
int h[N<<1],tot;
void add(int from,int to)
{
	e[++tot].to=to;
	e[tot].next=h[from];
	h[from]=tot;
}
int fa[N],siz[N],son[N],id[N],cnt;
void dfs1(int now)
{
	siz[now]=1;
	for(int i=h[now];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa[now]) continue;
		fa[to]=now;
		dfs1(to);
		if(siz[to]>siz[son[now]]) son[now]=to;
		siz[now]+=siz[to];
	}
}
void dfs2(int now)
{
	id[now]=++cnt;
	if(!son[now]) return;
	dfs2(son[now]);
	for(int i=h[now];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==son[now]||to==fa[now]) continue;
		dfs2(to);
	}
}
//---------------------------------------
struct tree
{
	int l,r,v,tag;
}t[N<<2];
void pushdown(int i)
{
	if(!t[i].tag) return;
	t[i<<1].v+=(t[i<<1].r-t[i<<1].l+1)*t[i].tag;
	t[i<<1|1].v+=(t[i<<1|1].r-t[i<<1|1].l+1)*t[i].tag;
	t[i<<1].tag+=t[i].tag;
	t[i<<1|1].tag+=t[i].tag;
	t[i].tag=0;
}	
void build(int i,int l,int r)
{
	t[i].l=l,t[i].r=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
}
void update(int i,int x,int y,int z)
{
	if(x<=t[i].l&&t[i].r<=y)
	{
		t[i].v+=(t[i].r-t[i].l+1)*z;
		t[i].tag+=z;
		return;
	}
	pushdown(i);
	int mid=(t[i].l+t[i].r)>>1;
	if(x<=mid) update(i<<1,x,y,z);
	if(mid<y) update(i<<1|1,x,y,z);
}
int query(int i,int x)
{
    if(t[i].l==x&&t[i].r==x) return t[i].v;
	pushdown(i);
	int mid=(t[i].l+t[i].r)>>1;
	if(x<=mid) return query(i<<1,x);
	else return query(i<<1|1,x);
}
int main()
{
	n=read(),m=read();
	a[1]=read();
	for(int i=2;i<=n;i++)
	{
		a[i]=read();
		int b=read();
		add(b,i);
	}
	dfs1(1);
	dfs2(1);
	build(1,1,n);
	for(int i=1;i<=n;i++)
		update(1,id[i],id[i],a[i]);
	while(m--)
	{
		char c=getchar();
		int m=0,x=0;
		if(c=='p')
		{
			m=read(),x=read();
			if(siz[m]==1) continue;
			update(1,id[m]+1,id[m]+siz[m]-1,x);
		}
		if(c=='u')
		{
			m=read();
			printf("%d\n",query(1,id[m]));
		}
	}
    return 0;
}  
2024/12/21 22:18
加载中...