BZOJ 1036 [ZJOI2008]树的统计Count 动态维护树上求和与求最大值 LCT板题

模板,也可以用树链剖分+线段树做O(nlog2)O(nlog^2)O(nlog2)

用LCT做O(nlog)O(nlog)O(nlog)在乘上一个大于30的常数…然后LCT比树剖慢一倍…

CODE

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

template<typename T>inline void read(T &num) {

	char ch; int flg = 1;

	while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;

	for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());

	num*=flg;

}

const int MAXN = 30005;

int n, q, u[MAXN], v[MAXN];

namespace LCT {

	#define ls ch[x][0]

	#define rs ch[x][1]

	int ch[MAXN][2], fa[MAXN];

	LL w[MAXN], sum[MAXN], mx[MAXN];

	bool rev[MAXN];

	inline bool isr(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; } //判断是否为根

	inline bool get(int x) { return x == ch[fa[x]][1]; }

	inline void upd(int x) { //上传

		sum[x] = sum[ls] + sum[rs] + w[x];

		mx[x] = max(w[x], max(mx[ls], mx[rs]));

	}

	inline void rot(int x) {

		int y = fa[x], z = fa[y], l = get(x), r = l^1;

		if(!isr(y)) ch[z][get(y)] = x;

		fa[ch[x][r]] = y; fa[y] = x; fa[x] = z;

		ch[y][l] = ch[x][r]; ch[x][r] = y;

		upd(y), upd(x);

	}

	inline void mt(int x) { if(rev[x]) rev[x] ^= 1, rev[ls] ^= 1, rev[rs] ^= 1, swap(ls, rs); } //下传

	void mtpath(int x) { if(!isr(x)) mtpath(fa[x]); mt(x); }

	inline void splay(int x) {

		mtpath(x);

		for(; !isr(x); rot(x))

			if(!isr(fa[x])) rot(get(x)==get(fa[x])?fa[x]:x);

	}

	inline int access(int x) { int y=0;

		for(; x; x=fa[y=x]) splay(x), ch[x][1]=y, upd(x);

		return y;

	}

	inline void bert(int x) { access(x), splay(x), rev[x] ^= 1; } //换根

	inline int sert(int x) { //找根

		access(x), splay(x);

		for(; ch[x][0]; x=ch[x][0]);

		return x;

	}

	inline void link(int x, int y) {

		bert(x);

		if(sert(y) == x) return;

		fa[x] = y;

	}

	inline void cut(int x, int y) {

		bert(x), access(y), splay(y);

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

		fa[x] = ch[y][0] = 0; upd(y);

	}

	inline void modify(int x, int val) {

		splay(x), w[x] = val, upd(x);

	}

	inline int split(int x, int y) {

		bert(x), access(y), splay(y);

		return y;

	}

	inline int querymax(int x, int y) {

		split(x, y); return mx[y];

	}

	inline int querysum(int x, int y) {

		split(x, y); return sum[y];

	}

}

using namespace LCT;

int main () {

	read(n); mx[0] = -0x7f7f7f7f; //把0设成-无穷,因为upd的时候会访问到

	for(int i = 1; i < n; ++i) read(u[i]), read(v[i]);

	for(int i = 1; i <= n; ++i) read(w[i]);

	for(int i = 1; i < n; ++i) link(u[i], v[i]);

	read(q);

	char s[10]; int x, y;

	while(q--) {

		scanf("%s", s); read(x), read(y);

		if(s[1] == 'M') printf("%d\n", querymax(x, y));

		else if(s[1] == 'S') printf("%d\n", querysum(x, y));

		else modify(x, y);

	}

}