【洛谷 P1501】 [国家集训队]Tree II（LCT）

Tree Ⅱ\(=\)【模板】LCT+【模板】线段树2。。

分别维护3个标记，乘的时候要把加法标记也乘上。

还有就是模数的平方刚好爆\(int\)，所以开昂赛德\(int\)就可以了。

我把初始化放在连边的那个循环里了，而那个循环是\(1\)到\(n-1\)的，所以第\(n\)个没初始化到。。\(WA\)了好久。

#include <cstdio>

#include <cstring>

#define YCH 51061

#define R register unsigned int

#define I inline void

#define lc c[x][0]

#define rc c[x][1]

#define mul(x, y) x *= y; x %= YCH

#define add(x, y) x += y; x %= YCH

const int MAXN = 100010;

inline int read(){

    int s = 0, w = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }

    while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }

    return s * w;

}

unsigned int f[MAXN], c[MAXN][2], v[MAXN], s[MAXN], st[MAXN], rt[MAXN], mt[MAXN], at[MAXN], sz[MAXN];

inline int nroot(R x){

	return c[f[x]][0] == x || c[f[x]][1] == x;

}

I pushup(R x){

	s[x] = (s[lc] + s[rc] + v[x]) % YCH;

	sz[x] = sz[lc] + sz[rc] + 1;

}

I pushr(R x){

	lc ^= rc; rc = lc ^ rc; lc ^= rc; rt[x] ^= 1;

}

I pushm(R x, R p){

	mul(s[x], p); mul(at[x], p);

	mul(mt[x], p); mul(v[x], p);

}

I pusha(R x, R p){

	add(s[x], p * sz[x]);

	add(at[x], p); add(v[x], p);

}

I pushdown(R x){

	if(mt[x] != 1){

		pushm(lc, mt[x]); pushm(rc, mt[x]);

		mt[x] = 1;

	}

	if(at[x]){

		pusha(lc, at[x]); pusha(rc, at[x]);

		at[x] = 0;

	}

	if(rt[x]){

		pushr(lc); pushr(rc);

		rt[x] = 0;

	}

}

I rotate(R x){

	R y = f[x], z = f[y], k = c[y][1] == x, w = c[x][!k];

	if(nroot(y)) c[z][c[z][1] == y] = x;

	c[x][!k] = y; c[y][k] = w; f[y] = x; f[x] = z;

	if(w) f[w] = y;

	pushup(y);

}

I splay(R x){

	R y = x, z = 0;

	st[++z] = y;

	while(nroot(y)) st[++z] = y = f[y];

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

	while(nroot(x)){

		y = f[x]; z = f[y];

		if(nroot(y)) (c[z][1] == y) ^ (c[y][1] == x) ? rotate(x) : rotate(y);

		rotate(x);

	}

	pushup(x);

}

I access(R x){

	for(R y = 0; x; x = f[y = x]){

	   splay(x); rc = y; pushup(x);

    }

}

I makeroot(R x){

	access(x); splay(x);

	pushr(x);

}

I split(R x, R y){

	makeroot(x); access(y); splay(y);

}

I link(R x, R y){

	makeroot(x);

	f[x] = y;

}

I cut(R x, R y){

	split(x, y);

	f[x] = c[y][0] = 0;

	pushup(y);

}

int n, m, a, b, x, y;

char opt;

int main(){

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

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

	   link(read(), read()), v[i] = mt[i] = 1;

	v[n] = mt[n] = 1;

	while(m--){

		opt = getchar(); while(opt != '-' && opt != '+' && opt != '*' && opt != '/') opt = getchar();

		a = read(); b = read();

		switch(opt){

			case '+' : x = read(); split(a, b); pusha(b, x); break;

			case '-' : x = read(); y = read(); cut(a, b); link(x, y); break;

			case '*' : x = read(); split(a, b); pushm(b, x); break;

			case '/' : split(a, b); printf("%d\n", s[b]); break;

		}

	}

	return 0;

}

巴特西

【洛谷 P1501】 [国家集训队]Tree II（LCT）

最新文章

热门文章