洛谷1501 Tree II（LCT，路径修改，路经询问）

这个题是一个经典的维护路径信息的题，对于路径上的修改，我们只需要把对应的链\(split\)上来，然后修改最上面的点就好，注意pushdown的时候的顺序是先乘后加

然后下传乘法标记的时候，记得把对应的\(add\)标记也要乘，因为就跟线段树的下传标记类似

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<vector>

#include<queue>

#include<cmath>

#include<map>

#include<set>

#define int long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 1e5+1e2;

const int mod = 51061;

int ch[maxn][3];

int n,m;

int sum[maxn],val[maxn];

int che[maxn],add[maxn];

int fa[maxn],size[maxn];

int st[maxn];

int rev[maxn];

int son(int x)

{

	if (ch[fa[x]][0]==x) return 0;

	else return 1;

}

bool notroot(int x)

{

	return ch[fa[x]][0]==x || ch[fa[x]][1]==x;

}

void update(int x)

{

	size[x]=size[ch[x][0]]+size[ch[x][1]]+1;

	sum[x]=(sum[ch[x][0]]+sum[ch[x][1]]+val[x])%mod;

}

void reverse(int x)

{

	swap(ch[x][0],ch[x][1]);

	rev[x]^=1;

}

void jia(int x,int d)

{

	sum[x]+=size[x]*d;

	sum[x]%=mod;

	val[x]+=d;

	val[x]%=mod;

	add[x]+=d;

	add[x]%=mod;

}

void cheng(int x,int d)

{

	sum[x]*=d;

	sum[x]%=mod;

	val[x]*=d;

	val[x]%=mod;

	add[x]*=d;

	add[x]%=mod;

	che[x]*=d;

	che[x]%=mod;

}

void pushdown(int x)

{

	if (che[x]!=1)

	{

		if (ch[x][0]) cheng(ch[x][0],che[x]);

		if (ch[x][1]) cheng(ch[x][1],che[x]);

		che[x]=1;

	}

	if (add[x])

	{

		if (ch[x][0]) jia(ch[x][0],add[x]);

		if (ch[x][1]) jia(ch[x][1],add[x]);

		add[x]=0;

	}

		if (rev[x])

	{

		if (ch[x][0]) reverse(ch[x][0]);

		if (ch[x][1]) reverse(ch[x][1]);

        rev[x]=0;

	}

}

void rotate(int x)

{

	int y=fa[x],z=fa[y];

	int b=son(x),c=son(y);

	if (notroot(y)) ch[z][c]=x;

	fa[x]=z;

	ch[y][b]=ch[x][!b];

	fa[ch[x][!b]]=y;

	ch[x][!b]=y;

	fa[y]=x;

	update(y);

	update(x);

}

void splay(int x)

{

	int y=x,cnt=0;

	st[++cnt]=y;

	while (notroot(y)) y=fa[y],st[++cnt]=y;

	while (cnt) pushdown(st[cnt--]);

	while (notroot(x))

	{

	  int y=fa[x],z=fa[y];

	  int b=son(x),c=son(y);

	  if (notroot(y))

	  {

	  	  if (b==c) rotate(y);

	  	  else rotate(x);

	  }

	  rotate(x);

	}

	update(x);

}

void access(int x)

{

	for (int y=0;x;y=x,x=fa[x])

	{

		splay(x);

		ch[x][1]=y;

		update(x);

	}

}

void makeroot(int x)

{

	access(x);

	splay(x);

	reverse(x);

}

int findroot(int x)

{

	access(x);

	splay(x);

	while (ch[x][0])

	{

	   pushdown(x);

	   x=ch[x][0];

	}

	return x;

}

void split(int x,int y)

{

	makeroot(x);

	access(y);

	splay(y);

}

void link(int x,int y)

{

   makeroot(x);

   if (findroot(y)!=x) fa[x]=y;

}

void cut(int x,int y)

{

	split(x,y);

	if (ch[x][0] || ch[x][1] || fa[x]!=y || ch[y][son(x)^1]) return;

	fa[x]=ch[y][0]=0;

}

char s[10];

signed main()

{

   n=read(),m=read();

   for (int i=1;i<=n;i++) che[i]=1,add[i]=0,val[i]=1;

   for (int i=1;i<n;i++)

   {

   	 int x=read(),y=read();

   	 link(x,y);

   }

   //split(1,3);

   //cout<<sum[3]<<endl;

   for(int i=1;i<=m;i++)

   {

   	 scanf("%s",s+1);

   	 if (s[1]=='+')

   	 {

   	 	int x=read(),y=read(),z=read();

   	 	split(x,y);

   	 	val[y]+=z;

   	 	val[y]%=mod;

   	 	sum[y]+=size[y]*z;

   	 	sum[y]%=mod;

   	 	add[y]+=z;

   	 	add[y]%=mod;

	 }

	 else

	 if (s[1]=='-')

	 {

	 	int x=read(),y=read(),xx=read(),yy=read();

	 	cut(x,y);

	 	link(xx,yy);

	 }

	 else

	 if (s[1]=='/')

	 {

	 	int x=read(),y=read();

	 	split(x,y);

	 	printf("%lld\n",sum[y]%mod);

	 }

	 else

	 {

	 	 int x=read(),y=read(),z=read();

	 	 //cout<<z<<endl;

	 	 split(x,y);

	 	 sum[y]*=z;

	     sum[y]%=mod;

	     val[y]*=z;

	     val[y]%=mod;

	     add[y]*=z;

	     add[y]%=mod;

	     che[y]*=z;

	     che[y]%=mod;

	 }

   }

   return 0;

}

巴特西

洛谷1501 Tree II（LCT，路径修改，路经询问）

最新文章

热门文章