树剖板子题 WA+TLE 求助
查看原帖
树剖板子题 WA+TLE 求助
64976
hewo楼主2021/9/1 11:42
#include<bits/stdc++.h>

using namespace std;

const int MX=1*1000000+1000;
#define LL long long
#define inf 0x3f3f3f3f
#define lson now<<1
#define rson now<<1|1

inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

LL n,m;
LL root,p;
LL w[MX];

struct tEdge
{
	LL to,next;
}edge[MX<<1];
LL head[MX],cnt=0ll;

inline void add(LL from,LL to)
{
	edge[++cnt].to=to,edge[cnt].next=head[from];
	head[from]=cnt;
}

LL deep[MX],size[MX],fa[MX];
LL son[MX];

LL dfn[MX],nfd[MX],idx=0ll;
LL top[MX];

inline void dfs1(LL now,LL father)
{
	size[now]=1ll;
	fa[now]=father;
	deep[now]=deep[father]+1ll;
	for(LL i=head[now];i;i=edge[i].next)
	{
		LL yt=edge[i].to;
		if(yt==father) continue;
		dfs1(yt,now);
		size[now]+=size[yt];
		if(size[yt]>size[son[now]]) son[now]=yt;
	}
}

inline void dfs2(LL now,LL t)
{
	dfn[now]=++idx,nfd[idx]=now;
	top[now]=t;
	if(son[now]) dfs2(son[now],t);
	for(LL i=head[now];i;i=edge[i].next)
	{
		LL yt=edge[i].to;
		if(yt!=fa[now]&&yt!=son[now])
		{
			dfs2(yt,yt);
		}
	}
}

struct tTree
{
	LL sum=0ll;
	LL lazytag;
	LL maxn;
}tree[MX<<2];

inline void pushup(LL now)
{
	tree[now].sum=tree[lson].sum+tree[rson].sum;
	tree[now].maxn=max(tree[lson].maxn,tree[rson].maxn);
}

inline void pushdown(LL now,LL l,LL r)
{
	LL mid=l+r>>1;
	tree[lson].lazytag+=tree[now].lazytag,tree[rson].lazytag+=tree[now].lazytag;
	tree[lson].sum+=(tree[now].lazytag)*(mid-l+1),tree[rson].sum+=(tree[now].lazytag)*(r-mid);
	tree[lson].maxn+=tree[now].lazytag,tree[rson].maxn+=tree[now].lazytag;
	tree[now].lazytag=0ll;
}

inline void build(LL now,LL l,LL r)
{
	if(l==r)
	{
		tree[now].sum=tree[now].maxn=w[nfd[l]];
		return ;
	}
	LL mid=l+r>>1;
	build(lson,l,mid),build(rson,mid+1,r);
	pushup(now);
}

inline void change(LL now,LL l,LL r,LL k,LL nl,LL nr)
{
	if(nl<=l&&nr>=r)
	{
		tree[now].sum+=(r-l+1)*k;
		tree[now].maxn+=k;
		tree[now].lazytag=k;
		return ;
	}
	LL mid=l+r>>1;
	pushdown(now,l,r);
	if(nl<=mid) change(lson,l,mid,k,nl,nr);
	if(nr>=mid+1) change(rson,mid+1,r,k,nl,nr);
	pushup(now);
}

inline LL get_sum(LL now,LL l,LL r,LL nl,LL nr)
{
	if(nl<=l&&nr>=r)
	{
		return tree[now].sum;
	}
	LL sum=0ll;
	LL mid=l+r>>1;
	pushdown(now,l,r);
	if(nl<=mid) sum+=get_sum(lson,l,mid,nl,nr);
	if(nr>=mid+1) sum+=get_sum(rson,mid+1,r,nl,nr);
	return sum;
}

inline LL get_max(LL now,LL l,LL r,LL nl,LL nr)
{
	if(nl<=l&&nr>=r)
	{
		return tree[now].maxn;
	}
	LL mid=l+r>>1;
	LL maxn=-inf;
	pushdown(now,l,r);
	if(nl<=mid) maxn=max(maxn,get_max(lson,l,mid,nl,nr));
	if(nr>=mid+1) maxn=max(maxn,get_max(rson,mid+1,r,nl,nr));
	return maxn;
}

inline LL path_sum(LL x,LL y)
{
	LL sum=0ll;
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]]) swap(x,y);
		sum+=get_sum(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(deep[x]<deep[y]) swap(x,y);
	sum+=get_sum(1,1,n,dfn[y],dfn[x]);
	return sum;
}

inline LL path_max(LL x,LL y)
{
	LL maxn=-inf;
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]]) swap(x,y);
		maxn=max(maxn,get_max(1,1,n,dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
	if(deep[x]<deep[y]) swap(x,y);
	maxn=max(maxn,get_max(1,1,n,dfn[y],dfn[x]));
	return maxn;
}

inline void path_add(LL x,LL y,LL k)
{
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]]) swap(x,y);
		change(1,1,n,k,dfn[top[x]],dfn[x]);
	}
	if(deep[x]<deep[y]) swap(x,y);
	change(1,1,n,k,dfn[y],dfn[x]);
}

inline LL tree_sum(LL x)
{
	return get_sum(1,1,n,dfn[x],dfn[x]+size[x]-1);
}

int main(int argc, char const *argv[])
{
	//freopen("debug.in","r",stdin);
	//freopen("debug.out","w",stdout);
	root=1ll;
	n=read();
	for(LL i=1;i<=n-1;i++)
	{
		LL u,v;
		u=read(),v=read();
		u++,v++;
		add(u,v),add(v,u);
	}
	memset(w,0,sizeof(w));
	dfs1(root,0);
	dfs2(root,root);
	build(1,1,n);
	m=read();
	while(m--)
	{
		char ins[3];
		scanf("%s",ins);
		if(ins[0]=='A')
		{
			LL u,v,k;
			u=read(),v=read(),k=read();
			u++,v++;
			path_add(u,v,k);
		}
		else if(ins[0]=='Q')
		{
			LL u;
			u=read();
			u++;
			printf("%lld\n",tree_sum(u));
		}
	}
	return 0;
}

大佬们请自行忽略下多余的函数

2021/9/1 11:42
加载中...