欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P1501 [国家集训队]Tree II(LCT 下推标记,LCT 维护树上信息)

程序员文章站 2022-04-06 23:48:31
...

P1501 [国家集训队]Tree II(LCT 下推标记,LCT 维护树上信息)


用 LCT 维护整棵树,splay 中要维护每个点的权值,子树节点个数以及子树和,为了优化复杂度还要维护下推标记。

这题有三种标记:翻转,加法,乘法

翻转标记的下推顺序不影响维护值,加法和乘法优先维护乘法下推标记,将乘法下推时要将子节点的子树和,节点权值,加法下推标记和乘法下推标记全部乘上乘法标记

加法下推标记则直接加即可,子树和要加上加法下推标记 * 子树节点个数


代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long ll;
int n,m;
const int mod = 51061;
inline int read(){
    int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
struct LCT {				//用splay维护原森林的连通,用到了splay的操作以及数组 
	int ch[maxn][2];		//ch[u][0] 表示 左二子,ch[u][1] 表示右儿子
	int f[maxn];			//当前节点的父节点 
	int tag[maxn];		//翻转标记,乘标记,加标记 
	int top,sta[maxn],sz[maxn];
	ll sum[maxn],val[maxn],add[maxn],mul[maxn];
	inline bool get(int x) {
    	return ch[f[x]][1] == x;
	}
	void init() {
		memset(f,0,sizeof f);
		memset(ch,0,sizeof ch);
		memset(tag,0,sizeof tag);
		memset(add,0,sizeof add);
		for (int i = 1; i <= maxn - 10; i++)
			sum[i] = val[i] = mul[i] = sz[i] = 1;
	}
	inline void pushup(int rt) {
		if (rt) {
			sz[rt] = 1; sum[rt] = val[rt];
			if (ch[rt][0]) sz[rt] += sz[ch[rt][0]], sum[rt] = (sum[rt] + sum[ch[rt][0]]) % mod;
			if (ch[rt][1]) sz[rt] += sz[ch[rt][1]], sum[rt] = (sum[rt] + sum[ch[rt][1]]) % mod;
		}
	}
	inline void pushdown(int rt) {
		if (tag[rt]) {
			int ls = ch[rt][0], rs = ch[rt][1];
			if (ls) swap(ch[ls][0],ch[ls][1]), tag[ls] ^= 1;
			if (rs) swap(ch[rs][0],ch[rs][1]), tag[rs] ^= 1;
			tag[rt] = 0;
		}
		if (mul[rt] != 1) {
			if (ch[rt][0]) {
				val[ch[rt][0]] = val[ch[rt][0]] * mul[rt] % mod;
				add[ch[rt][0]] = add[ch[rt][0]] * mul[rt] % mod;
				mul[ch[rt][0]] = mul[ch[rt][0]] * mul[rt] % mod;
				sum[ch[rt][0]] = sum[ch[rt][0]] * mul[rt] % mod;
			}
			if (ch[rt][1]) {
				val[ch[rt][1]] = val[ch[rt][1]] * mul[rt] % mod;
				add[ch[rt][1]] = add[ch[rt][1]] * mul[rt] % mod;
				mul[ch[rt][1]] = mul[ch[rt][1]] * mul[rt] % mod;
				sum[ch[rt][1]] = sum[ch[rt][1]] * mul[rt] % mod;
			}
			mul[rt] = 1;
		}
		if (add[rt]) {
			if (ch[rt][0]) {
				val[ch[rt][0]] = (val[ch[rt][0]] + add[rt]) % mod;
				add[ch[rt][0]] = (add[ch[rt][0]] + add[rt]) % mod;
				sum[ch[rt][0]] = (sum[ch[rt][0]] + 1ll * add[rt] * sz[ch[rt][0]]) % mod;
			}
			if (ch[rt][1]) {
				val[ch[rt][1]] = (val[ch[rt][1]] + add[rt]) % mod;
				add[ch[rt][1]] = (add[ch[rt][1]] + add[rt]) % mod;
				sum[ch[rt][1]] = (sum[ch[rt][1]] + 1ll * add[rt] * sz[ch[rt][1]]) % mod;
			}
			add[rt] = 0;
		}
	}
	inline bool isroot(int x) {
		return (ch[f[x]][0] != x) && (ch[f[x]][1] != x);
	}
 	inline void rotate(int x) {							//旋转操作,根据 x 在 f[x] 的哪一侧进行左旋和右旋 
	    int old = f[x], oldf = f[old];
		int whichx = get(x);
		if(!isroot(old)) ch[oldf][ch[oldf][1] == old] = x;		//如果 old 不是根节点,就要修改 oldf 的子节点信息
	    ch[old][whichx] = ch[x][whichx ^ 1];
	    ch[x][whichx ^ 1] = old;
	    f[ch[old][whichx]] = old;
	    f[old] = x; f[x] = oldf;
		pushup(old); pushup(x); 
	}
	inline void splay(int x) {								//将 x 旋到所在 splay 的根
		top = 0; sta[++top] = x;
		for (int i = x; !isroot(i); i = f[i]) sta[++top] = f[i]; //在 splay 中维护 下推标记 
		while(top) pushdown(sta[top--]);
    	for(int fa = f[x]; !isroot(x); rotate(x), fa = f[x]) {	//再把x翻上来
        	if(!isroot(fa))										//如果fa非根,且x 和 fa是同一侧,那么先翻转fa,否则先翻转x 
            	rotate((get(x) == get(fa)) ? fa : x);
        }
	}
	inline void access(int x) {					//access操作将x 到 根路径上的边修改为重边 
		int lst = 0;
		while(x > 0) {
			splay(x);
			ch[x][1] = lst;
			pushup(x);
			lst = x; x = f[x];
		}
	}
	inline void move_to_root(int x) {			//将 x 移到 x 所在树的根(不是所在splay的根,所在splay只是一条重链) 
		access(x); splay(x); tag[x] ^= 1; swap(ch[x][0],ch[x][1]);	
		//将 x 移到 根之后 x 是深度最低的点,这条重链、这棵splay上所有点的深度颠倒,
		//所有的点的左子树的点应该到右子树,因此要翻转这棵splay的左右子树
	}
	inline int findroot(int x) {
		access(x); 
		splay(x);
		int rt = x;
		while(ch[rt][0]) rt = ch[rt][0];
		return rt;
	}
	inline void link(int x,int y) {
		move_to_root(x); f[x] = y; splay(x);
	}
	inline void cut(int x,int y) {
		move_to_root(x); access(y); 
		splay(y); ch[y][0] = f[x] = 0;
		pushup(y);
	}
}tree;
int x,y,u,v,k[maxn];
char op[10];
int main() {
	n = read(); m = read();
	tree.init();
	for (int i = 1; i < n; i++) {
		u = read(); v = read();
		tree.link(u,v);
	}
	while(m--) {
		scanf("%s",op);
		if (op[0] == '+') {
			u = read(), v = read(), x = read();
			tree.move_to_root(u);
			tree.access(v);
			tree.splay(v);
			tree.val[v] = (tree.val[v] + x) % mod;
			tree.add[v] = (tree.add[v] + x) % mod;
			tree.sum[v] = (tree.sum[v] + 1ll * x * tree.sz[v]) % mod;
		} 
		if (op[0] == '-') {
			u = read(); v = read(); x = read(); y = read();
			tree.cut(u,v);
			tree.link(x,y);
		}
		if (op[0] == '*') {
			u = read(); v = read(); x = read();
			tree.move_to_root(u);
			tree.access(v);
			tree.splay(v);
			tree.val[v] = tree.val[v] * x % mod;
			tree.mul[v] = tree.mul[v] * x % mod;
			tree.add[v] = tree.add[v] * x % mod;
			tree.sum[v] = tree.sum[v] * x % mod;
		}
		if (op[0] == '/') {
			u = read(); v = read();
			tree.move_to_root(u);
			tree.access(v);
			tree.splay(v);
			printf("%lld\n",tree.sum[v]);
		}
	}
	return 0;
}
相关标签: LCT LCT下推标记