[spoj QTREE 6 7] Query on a tree VI VII

这两题中, 定义: u和v连通 iff u到v简单路径 (包括端点) 上所有点同色. 点数, 询问数 ≤ 10^5, |权值| ≤ 10^9. - QTREE 6: 切换点的颜色(黑白)/询问某点所在连通块大小 - QTREE 7: 切换点的颜色(黑白)/修改点权/询问某点所在连通块中的最大点权

LCT维护子树信息

LCT维护子树信息（子树信息LCT） LCT维护边权（边权LCT） 知识点讲解 by neither_nor

LCT支持简单的子树查询.

LCT上的实边不和原树中的边对应. 一个实边连通块是一棵二叉搜索树, 它的中序遍历是原树中的一条链.

LCT上的虚边和原树中的边对应, 但不完全等同. 如果LCT上有一条x->y的虚边, 那么原树上有一条x->y所在重链顶部的边.

如果一个点是某棵Splay的根结点, 那么以它为根的子LCT对应原树上的一棵子树.

一棵子LCT是原树中的一段重链和挂在这段重链上的子树.

对于LCT中的每个点, 维护它所有虚子树 (由一条虚边连接的子LCT) 的信息和, 以它为根的子LCT的信息和. 以它为根的子LCT的信息和 = 自己 + 虚子树信息和 + 实子树信息和. access操作会切换虚实边, link操作会添加虚边; 适时地将信息加入或移出 "虚子树信息和" 即可. 所以, 维护的信息需要具备可减性.

link y to x, 不光要把y设成根, 还要对x access+splay, 否则会引起一连串的更新需求.

QTREE 6

LCT

对于每个点, 维护子LCT根结点的答案. 查询的时候换根即可.

由于得支持切换颜色, 分别维护LCT根结点为黑色的虚子树信息和, LCT根结点为白色的虚子树信息和. 由于得支持换根, 还要对称地维护把重链翻转后的答案.

BZOJ上的时限较紧, 建树的时候用DFS直接定向以替代link, 减小常数 (然后卡着时限过).

轻重链剖分

只考虑每个点所在连通块与以自己为根的子树的交集. 查询的时候爬到连通块的最高点top(u). 令白色=0, 黑色=1, 维护链上颜色之和即可.

为了方便切换颜色, 同时维护子树关于黑/白的答案之和: cnt(x, black/white). 以白->黑为例. fa(u)~fa(top(u))关于白色的答案减少1+cnt(u, white). 切换点u为黑色. fa(u)~fa(top(u))关于黑色的答案增加1+cnt(u, black).

轻重链剖分+树状数组.

相比较而言, LCT理论复杂度更优, 然而它的常数抵消了这一优点.

Code

LCT解法的代码.

const int N = 1e5;

struct Node {
	Node* ch[2], * fa;
	int t, cnt[2][2], icnt[2];
	bool p[2], b, rev;

	Node(int c=1);

	void setf(Node* f, int _t)
	{
		t = _t;
		fa = f;
		t >= 0 ? f->ch[t] = this : 0;
	}

	void up()
	{
		p[b^1] = false;
		p[b] = ch[0]->p[b] && ch[1]->p[b];
		rep (k, 0, 2) {
			cnt[k][b^1] = ch[k]->cnt[k][b^1];
			cnt[k][b] = ch[k]->cnt[k][b] + (ch[k]->p[b] ? 1 + icnt[b] + ch[k^1]->cnt[k][b] : 0);
		}
	}

	void reverse()
	{
		rev ^= 1;
		swap(ch[0], ch[1]);
		swap(cnt[0], cnt[1]);
		ch[0]->t = 0;
		ch[1]->t = 1;
	}

	void down()
	{
		if (rev) {
			ch[0]->reverse();
			ch[1]->reverse();
			rev = false;
		}
	}
} nodes[N+1], null_node(0), * nil = &null_node;

Node::Node(int c): fa(0), t(-1), b(true), rev(false)
{
	ch[0] = ch[1] = nil;
	cnt[0][0] = cnt[1][0] = icnt[0] = icnt[1] = 0;
	cnt[0][1] = cnt[1][1] = c;
	p[0] = c^1;
	p[1] = true;
}

inline void rot(Node* y)
{
	Node* x = y->fa;
	int t = y->t;
	y->setf(x->fa, x->t);
	y->ch[t^1]->setf(x, t);
	x->setf(y, t^1);
	x->up();
}

void splay(Node* x)
{
	static Node* S[N], * y;
	int top = 0;
	for (y = x; y->t >= 0; y = y->fa) S[top++] = y;
	for (y->down(); top; S[--top]->down()) ;

	while (x->t >= 0) {
		if ((y = x->fa)->t >= 0)
			rot(x->t ^ y->t ? x : y);
		rot(x);
	}
	x->up();
}

void access(Node* x)
{
	for (Node* y = nil; x; y = x, x = x->fa) {
		splay(x);
		
		Node* z = x->ch[1];
		z->t = -1;

		x->icnt[0] += z->cnt[0][0] - y->cnt[0][0];
		x->icnt[1] += z->cnt[0][1] - y->cnt[0][1];

		y->setf(x, 1);

		x->up();
	}
}

inline void make_root(Node* x)
{
	access(x);
	splay(x);
	x->reverse();
}

inline int query(Node* x)
{
	make_root(x);
	return x->cnt[0][x->b];
}

inline void toggle(Node* x)
{
	access(x);
	splay(x);
	x->b ^= 1;
	x->up();
}

struct Edge {
	int to, nxt;
} E[2*N];

int ptr = 1, adj[N+1];

inline void add(int x, int y)
{
	E[ptr] = (Edge){y, adj[x]};
	adj[x] = ptr++;
}

void dfs(int u, int p)
{
	for (int i = adj[u]; i; i = E[i].nxt) {
		int v = E[i].to;
		if (v == p) continue;
		dfs(v, u);
		nodes[u].icnt[0] += nodes[v].cnt[0][0];
		nodes[u].icnt[1] += nodes[v].cnt[0][1];
		nodes[v].setf(nodes+u, -1);
	}
	nodes[u].up();
}

int main()
{
	int n;
	scanf("%d", &n);
	rep (i, 0, n-1) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs(1, 0);
	int m;
	scanf("%d", &m);
	while (m--) {
		int t, u;
		scanf("%d%d", &t, &u);
		if (t)
			toggle(nodes+u);
		else
			printf("%d\n", query(nodes+u));
	}
	return 0;
}

QTREE 7

LCT

和 QTREE 6 类似, 由于最大值不具备可减性, 所以用大根堆维护.

轻重链剖分

原理和 QTREE 6 以及LCT解法类似, 但实现上做出一些调整. 原来是区间修改, 单点查询. 现在区间修改不太方便, 所以改做单点修改, 区间查询.

每个点两个大根堆, 维护轻边连接的子树关于黑/白的答案. 查询的时候除了向上爬, 还要沿重链向下查一查.

SPOJ 16580 QTREE7 - Query on a tree VII by Fuxey Orz

Code

const int N = 1e5, inf = 1e9 + 1;

template<typename T>
struct Heap {
	multiset<T> S;
	T mx;
	
	Heap(): mx(-inf) {}

	T top()
	{
		return mx;
	}

	void push(const T& v)
	{
		if (v == -inf) return;
		S.insert(v);
		mx = max(v, mx);
	}

	void erase(const T& v)
	{
		if (v == -inf) return;
		S.erase(S.find(v));
		mx = S.empty() ? -inf : *S.rbegin();
	}
};

struct Node {
	Node* ch[2], * fa;
	int t, w, mx[2][2];
	bool b, rev, p[2];
	Heap<int> imx[2];

	Node();

	void setf(Node* f, int _t)
	{
		t = _t;
		fa = f;
		t >= 0 ? f->ch[t] = this : 0;
	}

	void up()
	{
		p[b] = ch[0]->p[b] && ch[1]->p[b];
		p[b^1] = false;
		rep (k, 0, 2) {
			mx[k][b^1] = ch[k]->mx[k][b^1];
			mx[k][b] = ch[k]->mx[k][b];
			if (ch[k]->p[b])
				mx[k][b] = max(mx[k][b], max(max(w, ch[k^1]->mx[k][b]), imx[b].top()));
		}
	}

	void reverse()
	{
		rev ^= 1;
		swap(ch[0], ch[1]);
		swap(mx[0], mx[1]);
		ch[0]->t = 0;
		ch[1]->t = 1;
	}

	void down()
	{
		if (rev) {
			ch[0]->reverse();
			ch[1]->reverse();
			rev = false;
		}
	}
} nodes[N+1], * nil = nodes;

Node::Node(): fa(0), t(-1), w(-inf), b(false), rev(false)
{
	ch[0] = ch[1] = nil;
	fill_n(*mx, 4, -inf);
	p[0] = p[1] = true;
}

inline void rot(Node* y)
{
	Node* x = y->fa;
	int t = y->t;
	y->setf(x->fa, x->t);
	y->ch[t^1]->setf(x, t);
	x->setf(y, t^1);
	x->up();
}

void splay(Node* x)
{
	static Node* S[N], * y;
	int top = 0;
	for (y = x; y->t >= 0; y = y->fa) S[top++] = y;
	for (y->down(); top; S[--top]->down()) ;

	while (x->t >= 0) {
		if ((y = x->fa)->t >= 0)
			rot(x->t ^ y->t ? x : y);
		rot(x);
	}
	x->up();
}

void access(Node* x)
{
	for (Node* y = nil; x; y = x, x = x->fa) {
		splay(x);

		Node* z = x->ch[1];
		z->t = -1;
		y->setf(x, 1);
		
		x->imx[0].erase(y->mx[0][0]);
		x->imx[1].erase(y->mx[0][1]);
		
		x->imx[0].push(z->mx[0][0]);
		x->imx[1].push(z->mx[0][1]);

		x->up();
	}
}

inline void make_root(Node* x)
{
	access(x);
	splay(x);
	x->reverse();
}

inline void link(Node* x, Node* y)
{
	make_root(y);
	access(x);
	splay(x);
	y->setf(x, -1);
	x->imx[0].push(y->mx[0][0]);
	x->imx[1].push(y->mx[0][1]);
	x->up();
}

inline int query(Node* x)
{
	make_root(x);
	return x->mx[0][x->b];
}

pair<int, int> edge[N-1];

int main()
{
	int n;
	scanf("%d", &n);
	rep (i, 0, n-1)
		scanf("%d%d", &edge[i].first, &edge[i].second);
	rep (i, 1, n+1) {
		int c;
		scanf("%d", &c);
		nodes[i].b = c;
	}
	rep (i, 1, n+1) {
		scanf("%d", &nodes[i].w);
		nodes[i].up();
	}
	rep (i, 0, n-1)
		link(nodes + edge[i].first, nodes + edge[i].second);
		
	int m;
	scanf("%d", &m);
	while (m--) {
		int o, u;
		scanf("%d%d", &o, &u);
		Node* x = nodes + u;
		if (o) {
			access(x);
			splay(x);
			if (o == 1)
				x->b ^= 1;
			else
				scanf("%d", &x->w);
			x->up();
		} else {
			printf("%d\n", query(x));
		}
	}
	return 0;
}