SPOJ Query On A Tree IV 题解

一个边分治套线段树套堆的题目

比较难写但是有不小的启发

思路来源和代码都抄自 [SPOJ-QTREE4]QUERY ON A TREE IV 题解 | KSKUN' s Blog

简要题意

给定一个 \(n\) 个点的带边权树， 点的编号为 \(1\sim n\)， 初始树上所有节点都是白色的， 要求维护两个操作：

1. \(\rm {C\ a}\) 反转 \(a\) 节点的颜色（白色变成黑色或者黑色变成白色）
2. \(\rm A\) 查询树上最远的两个白点的距离

特别的，进行 \(\rm A\) 操作时如果树上没有白点输出 They have disappeared.

\(N\le 10^5, Q\le 10^5, -10^3\le c\le 10^3\)

题目链接
谷的RMJ
原地址

做法

在线版：

树上的问题太难了，先把这个问题丢到一个序列里面做看看有没有什么启发性的做法

问题变成给你一个 \(01\) 序列，询问变成每次反转一个数，以及查询两个距离最远的 \(0\) 相隔的距离

这个问题如果是静态的（忽略操作 \(1\)）就是双指针扫一下两端第一个 \(0\) 的位置就可以了

但是这个做法没什么前途，因为在带修的情况下每次都要重新确定答案（这相当于维护序列的前缀和和后缀和，每次修改要变动很多东西），而且放到树上不太现实。

考虑一种过中点的分治，每次取序列的中点，把序列分为左半和右半两个子序列，维护左半子序列和右半子序列所有为 \(1\) 的点到中点的距离，左半和右半各取一个 \(\max\) 合起来就是横跨中点的答案，然后递归左子序列和右子序列，那么当前序列的答案就是 \(\max(self\_max,left\_max,right\_max)\)

考虑这个分治的原因是一个点至多属于 \(\log\) 个子序列，修改是 \(\log\) 的

这个种分治带修很好做，这东西长得就像线段树的形式自然可以像线段树那样维护

至于带修，每个节点维护左子序列所有点到中点的距离的一个大根堆，右子序列所有点到中点距离的一个大根堆，把堆顶所有黑色节点弹出，取两个堆顶即可，修改的时候，白改黑就是把点置为黑色，更新答案，黑改白就是把点置为白色，把点重新插进堆里面去，更新答案

好，序列上做完了考虑把这东西塞到树上去

原来序列过中点分治现在显然就是边分治（因为每次要把树分成两半，多了不好合并答案）

对分出来的两个子树分别开个堆维护最大值，然后接下来对子树再进行分治，和上面完全是一模一样的道理

注意有两个问题就是树上跟序列上不太一样，给一个点不好确定它在每一层中心边的左侧还是右侧，这个可以对每个点开一个长度为 \(\log\) 的数组，然后维护它每一层属于哪条中心边的哪一侧

而且也不好直接做线段树的区间编号，需要用类似动态开点的方式维护编号，更新很难递归，直接自底向上更新就好了

具体可以看一下示例代码

#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <vector>

typedef long long ll;

const int N = 1e5 + 10, M = 2e5 + 10, inf = 0x7f7f7f7f;
int h[N], e[M], ne[M], w[M], idx;
int n;

void add(int x, int y, int c){
	e[idx] = y, ne[idx] = h[x], w[idx] = c, h[x] = idx++;
}

namespace new_tree{
	int h[N << 1], e[M << 1], ne[M << 1], w[M << 1], idx;
	int NodeNum;
	//节点的颜色, false为白, true为黑
	bool color[N << 1];
	int WhiteNum;

	void add(int x, int y, int c){
		e[idx] = y, ne[idx] = h[x], w[idx] = c, h[x] = idx++;
	}
	
    //重建树
	void rebuild(int u, int fa){
		int ff = 0;
		for(int i = ::h[u]; ~i; i = ::ne[i]){
			int v = ::e[i];

			if(v == fa)
				continue;
			if(!ff){
				add(u, v, ::w[i]);
				add(v, u, ::w[i]);
				ff = u;
			}
			else{
				int tmp = ++NodeNum;
				color[tmp] = 1;
				add(tmp, ff, 0);
				add(ff, tmp, 0);
				add(tmp, v, ::w[i]);
				add(v, tmp, ::w[i]);
				ff = tmp;
			}
			rebuild(v, u);
		}
	}

	/****************树上分治部分****************/
	bool vis[M << 1];
	int siz[N << 1];
	int MinMax;
	int core;

	/********************算中心边*********************/
	void getsiz(int u, int fa){
		siz[u] = 1;
		for(int i = h[u]; ~i; i = ne[i]){
			int v = e[i];
			if(vis[i] || v == fa)
				continue;

			getsiz(v, u);
			siz[u] += siz[v];
		}
	}


	void getcore(int u, int tot, int fa){
		for(int i = h[u]; ~i; i = ne[i]){
			int v = e[i];
			if(v == fa || vis[i])
				continue;
			int Maxn = std::max(siz[v], tot - siz[v]);

			if(Maxn < MinMax){
				MinMax = Maxn;
				core = i;
			}

			getcore(v, tot, u);
		}
	}


	/******************分治结构需要维护的信息**************/
	//树上边分治每次把树分成两个部分
	//对每个结构开一个优先队列维护双端最大值
	//具体来说, 结构类似于线段树
	struct dis_info{
		int u, d;
		bool operator < (const dis_info &b) const {
			return d < b.d;
		}
	};

	std::priority_queue<dis_info> q[N << 1][2];
	int cnt;

	struct Node{
		//div 是一个分治结构的编号
		int div, side, dis;
	};
	//对于每个节点, 维护每层它属于哪个分治结构（所属中心边编号）, 方便更新
	//类似于线段树, 维护每层它属于哪个区间
	//log层, 空间n log n
	
	std::vector<Node> node[N << 1];

	struct Seg_Node{
		int ls, rs, core_w, maxn;
	}tr[N << 1];
	/********************更新分治结构信息******************/

	//p是分治结构编号
	void upd(int p){
		while(!q[p][0].empty() && color[q[p][0].top().u])
			q[p][0].pop();
		while(!q[p][1].empty() && color[q[p][1].top().u])
			q[p][1].pop();

		//如果左侧或者右侧没有白点
		if(q[p][0].empty() || q[p][1].empty())
			tr[p].maxn = 0;
		else
			tr[p].maxn = q[p][0].top().d + q[p][1].top().d + tr[p].core_w;

		//和左右子树取max
		if(tr[p].ls)	tr[p].maxn = std::max(tr[p].maxn, tr[tr[p].ls].maxn);
		if(tr[p].rs)	tr[p].maxn = std::max(tr[p].maxn, tr[tr[p].rs].maxn);
	}

	void set_white(int u){
		//自底向上
		for(int i = node[u].size() - 1; i >= 0; i--){
			Node d = node[u][i];
			//把节点重新入队
			q[d.div][d.side].push({u, d.dis});
			upd(d.div);
		}
	}

	void set_black(int u){
		//自底向上
		for(int i = node[u].size() - 1; i >= 0; i--){
			Node d = node[u][i];
			upd(d.div);
		}
	}
	/**********************裁剪分治结构********************/

	//计算结构内信息
	//t是结构编号, side是在结构哪一侧
	void calc_dis(int u, int fa, int d, int t, int side){
		//白点需要计算距离
		if(!color[u]){
			q[t][side].push({u, d});
			node[u].push_back({t, side, d});
		}
		for(int i = h[u]; ~i; i = ne[i]){
			int v = e[i];
			if(v == fa || vis[i])
				continue;
			calc_dis(v, u, d + w[i], t, side);
		}
	}

	int dfs(int x){
		MinMax = NodeNum;
		getsiz(x, 0);

		core = -1;
		getcore(x, siz[x], 0);

		//没有边可以找了
		if(core == -1)	return 0;
		int from = e[core], to = e[core ^ 1];
		
		//删掉这一条边
		vis[core] = vis[core ^ 1] = true;

		//新结构的编号
		int t = ++cnt;
		tr[t].core_w = w[core];
		calc_dis(from, 0, 0, t, 0);
		calc_dis(to, 0, 0, t, 1);

		//构建分治结构
		tr[t].ls = dfs(from);
		tr[t].rs = dfs(to);
		upd(t);
		return t;
	}

	/****************主体框架部分****************/
	void solve(){
		WhiteNum = ::n;
		memset(h, -1, sizeof h);
		NodeNum = ::n;
		rebuild(1, -1);
		
		dfs(1);
		int query;

		scanf("%d", &query);
		for(int i = 1; i <= query; i++){
			char op[2];
			scanf("%s", op);

			if(op[0] == 'A'){
				if(!WhiteNum){
					puts("They have disappeared.");
				}
				else if(WhiteNum == 1){
					puts("0");
				}
				else{
					printf("%d\n", tr[1].maxn);
				}
			}

			else{
				int u;
				scanf("%d", &u);
				color[u] ^= 1;
				if(color[u]){
					set_black(u);
					WhiteNum--;
				}
				else{
					set_white(u);
					WhiteNum++;
				}
			}
		}
	}
}

int main(){
	memset(h, -1, sizeof h);
	scanf("%d", &n);
	for(int i = 1; i < n; i++){
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		add(x, y, c), add(y, x, c);
	}
	new_tree::solve();
	return 0;
}

这种比较大型的数据结构代码一定要想清楚实现细节再写，搞清楚在干什么再动笔

否则会调很久很久

离线版

上面的在线做法好像不太聪明啊

上面的做法相当于每一次询问都对整个树重新做了一次边分治，只是注意到了每次至多修改 \(\log\) 层的信息所以可以用线段树做到比较快的修改而已

从点分治板子里我们意识到一件事情

树上分治是可以 \(Q\) 个询问一起做的，因为每次分治得到的两侧信息不会有太大的变化，没必要重新算一遍，可以重复利用

所以其实可以把线段树砍掉，不需要每次维护修改对全局答案的影响，直接 \(Q\) 个询问一起做，直接边分治，每次两侧的答案用一个大根堆维护，然后依次执行询问，还是类似，白变黑直接变，黑变白先把点插进堆里再变，然后每次询问把堆顶所有黑点弹出然后再取堆顶就行了

使用一些配对堆或者斐波那契堆科技可以把复杂度再干掉一个 $\log $（堆插入）， 时间复杂度是 \((n+Q)\log n\)， 空间复杂度如果及时析构可以做到 \(O(n)\)，大概可以卡一个最优解了

代码没写，只写了在线版的