BZOJ 线段树 1969: [Ahoi2005]LANE 航线规划

1969: [Ahoi2005]LANE 航线规划

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 132 Solved: 55
[ Submit][ Status]

Description

对Samuel星球的探险已经取得了非常巨大的成就，于是科学家们将目光投向了Samuel星球所在的星系——一个巨大的由千百万星球构成的Samuel星系。星际空间站的Samuel II巨型计算机经过长期探测，已经锁定了Samuel星系中许多星球的空间坐标，并对这些星球从1开始编号1、2、3……。一些先遣飞船已经出发，在星球之间开辟探险航线。探险航线是双向的，例如从1号星球到3号星球开辟探险航线，那么从3号星球到1号星球也可以使用这条航线。例如下图所示：

在5个星球之间，有5条探险航线。 A、B两星球之间，如果某条航线不存在，就无法从A星球抵达B星球，我们则称这条航线为关键航线。显然上图中，1号与5号星球之间的关键航线有1条：即为4-5航线。然而，在宇宙中一些未知的磁暴和行星的冲撞，使得已有的某些航线被破坏，随着越来越多的航线被破坏，探险飞船又不能及时回复这些航线，可见两个星球之间的关键航线会越来越多。假设在上图中，航线4-2（从4号星球到2号星球）被破坏。此时，1号与5号星球之间的关键航线就有3条：1-3，3-4，4-5。小联的任务是，不断关注航线被破坏的情况，并随时给出两个星球之间的关键航线数目。现在请你帮助完成。

Input

第一行有两个整数N，M。表示有N个星球（1< N < 30000），初始时已经有M条航线（1 < M < 100000）。随后有M行，每行有两个不相同的整数A、B表示在星球A与B之间存在一条航线。接下来每行有三个整数C、A、B。C为1表示询问当前星球A和星球B之间有多少条关键航线；C为0表示在星球A和星球B之间的航线被破坏，当后面再遇到C为1的情况时，表示询问航线被破坏后，关键路径的情况，且航线破坏后不可恢复； C为-1表示输入文件结束，这时该行没有A,B的值。被破坏的航线数目与询问的次数总和不超过40000。

Output

对每个C为1的询问，输出一行一个整数表示关键航线数目。注意：我们保证无论航线如何被破坏，任意时刻任意两个星球都能够相互到达。在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。

Sample Input

5 5
1 2
1 3
3 4
4 5
4 2
1 1 5
0 4 2
1 5 1
-1

Sample Output

1
3

HINT

Source

题意：中文题目就不解释了。

思路：我们先考虑如果没有删除边的操作，只有询问怎么做。我们可以先求出边-双连通分量。那么整个图就是一颗树了。其中树边就是题目所说的“关键边”。那么u到v的路径的关键边数量相当于就是树上u到v的距离，那么首先知道u，v的lca，然后我们如果事先求出了树上每个点的深度，那么u到v的距离就是deep(u)-deep(lca)+deep(v)-deep(lca) 。怎么快速求出两个点的lca呢？我们可以用rmq 来求，rmq预处理是O(nlogn) ,查询时O(1)....我们要怎么查询呢？

我们看一下这棵树：

/ \

2 3

/ | \ |

4 5 6 7

那么我们从根开始dfs ，那么我们得到的时间序是: 1(1),2(2),4(3),2(2),5(4),2(2),6(5),2(2),1(1),3(6),7(7),3(6),1(1)

其中括号中的表示某个点第一次遇到的时间，括号外的就是点的编号。发现是么没有，如果我们询问的是4和5的lca，那么lca应该在.....4(3),2(2),5(4) 之中，然而，其中2是最早遇到的，所以lca就是2，再看2和7，那么lca应该在2(2),4(3),2(2),5(4),2(2),6(5),2(2),1(1),3(6),7(7)之中其中时间最早的是1，所以他们lca就是1。对于更一般的情况，我们时间序列的形式是怎么样的，我们设根是rt，他的时间是1，那么时间序的形式如下rt(1) -> (左边第一颗子树)->rt(1)->（左边第二颗子树）->rt(1)->......（右边第一颗子树）->rt(1), 注意这个形式是递归的，那么如果第一点在第一颗子树，第二个点在第二颗子树，那么他们之间的所有时间序中时间最小的是rt，rt就是他们的lca，如果两个点在同一颗子树，只需要要看那一颗子树的那段时间序，直到两个点在两颗子树中，这时候那段序列里面时间最小的点就是他们的lca。不懂没关系，画几个图，把时间序列写出来，按照我说的模拟一下求lca的过程，就知道了。

好！这时候我们已经知道要怎么求lca了，就是u在时间序中的起始位置和v在时间序中起始位置之间时间最小的点。我们就可以用rmq来统计某个区间上的时间的最小值了。求出了lca，两个点的距离就出来了。

到这里为止，我们已经知道如何快速求出一个图任意两点之间的“关键边”，但可惜的是，题目中有删除边的操作。那要怎么破？我们要关心的量是lca和每个点的深度，看下我们应该如何维护这两个量。

我们把所有的操作反过来做，就是从经过所有这些操作后剩下的图开始，然后从后往前的操作，那么之前的删边，相当于就是加一条边了，这样看起来会好做一点。我们不妨设最后的图是一颗树（如果不是的话，我们可以在原来的操作里面再多加一些删除边的操作，让最后的图变成一棵树），那么当我们要加一条边进这颗树的时候，这棵树必定会出现一个环，那么这个环上的所有的树边都应该要删除，删除的操作可以用并查集把环上点并到一起。那么LCA其实并没有怎么改变，只是从原来的LCA(u,v)变成了find(LCA(find(u),find(v)) 其中find(x) 是找到并查集中u的根。很好！第一个lca的维护已经解决了。

接下来看如何维护一个点的深度。假设我们删掉一条边(u,fa(u)) fa(u) 表示的是u的父亲节点。那么u节点对应的子树里面的所有节点的深度都需要减1，这时候我们的时间戳又起作用了，我们可以在dfs的时候记录每个点对应的最早时间L(就是根的时间）和他的子孙中最大的时间R（就是最有边的叶子的时间），不难想到一个节点的所有子孙的时间值能够涵盖[L+1,R] 中的每一个整数。所以我们可以用线段树来维护一颗子树中的深度总和。每删掉一条边（u,fa(u)）就是将L[u],R[u]中的值全部-1。这样就实现了一个节点所有子孙的深度都-1的效果。

这道题目说到这里基本上就已经解出来了。剩下就是考验你码力的时候了。然后的话由于点有30000，递归最多要到30000层，所以直接递归的dfs可能会溢出，所以我用的是栈模拟递归。虽然是这么说，但是别人的用递归的代码还是过了Orz。。。。

最后附上两个链接：

http://blog.sina.com.cn/s/blog_51cea4040100gjwg.html

http://blog.sina.com.cn/s/blog_51cea4040100gjxe.html

这两个是这道题目的题解。如果我讲得不够清楚，可以结合这两个里面的看，相信你们一定能搞懂这道题目的！而且里面有一个很不错的线段树的写法，大家可以参考一下哦

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 30000 + 10;
const int maxm = 100000 + 10;
const int maxq = maxm + 40000 + 10;

struct Edge
{
	int u, v;
	Edge() { }
	Edge(int u, int v)
		:u(u), v(v) { }
	bool operator<(const Edge&e) const
	{
		if (u == e.u) return v < e.v;
		return u < e.u;
	}
	bool operator==(const Edge&e) const
	{
		return e.u == u&&e.v == v;
	}
}edges[maxm];

struct Oper
{
	int c, a, b;
	int ans;
	Oper() { }
	Oper(int c, int a, int b)
		:c(c), a(a), b(b) { }
}oper[maxq];

struct SegmentTree
{
	int sum[maxn << 2];
	int col[maxn << 2];
	void PushUp(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }
	void PushDown(int rt, int l, int r)
	{
		if (col[rt])
		{
			col[rt << 1 | 1] += col[rt];
			col[rt << 1] += col[rt];
			int m = (l + r) >> 1;
			sum[rt << 1] += col[rt] * (m - l + 1);
			sum[rt << 1 | 1] += col[rt] * (r - m);
			col[rt] = 0;
		}
	}
	void Update(int L, int R, int x, int l, int r, int rt)
	{
		if (L <= l&&r <= R)
		{
			sum[rt] += x*(r - l + 1);
			col[rt] += x;
			return;
		}
		PushDown(rt, l, r);
		int m = (l + r) >> 1;
		if (L <= m) Update(L, R, x, lson);
		if (R>m) Update(L, R, x, rson);
		PushUp(rt);
	}
	int Query(int p, int l, int r, int rt)
	{
		if (l == r) return sum[rt];
		int m = (l + r) >> 1;
		PushDown(rt, l, r);
		if (p <= m) return Query(p, lson);
		else return Query(p, rson);
	}
	void init()
	{
		memset(sum, 0, sizeof(sum));
		memset(col, 0, sizeof(col));
	}
}seg_tree;

int N, M, Q;
int dfn, pre[maxn], post[maxn];
bool vis[maxm], del[maxm];
int rmq[2 * maxm], tot;
int dfn_to_node[maxn];
int rmq_pos[maxn];
int anc[2 * maxm][19];
int dep[maxn];
vector<int> G[maxn];
int fa[maxn], p[maxn];

int find(int x)
{
	if (x == p[x]) return x;
	return p[x] = find(p[x]);
}
void make_rmq()
{
	for (int i = 0; i < tot; ++i)
		anc[i][0] = rmq[i];
	for (int j = 1; (1<<j)<=tot;++j)
	for (int i = 0; i + (1 << j) - 1 < tot; ++i)
		anc[i][j] = min(anc[i][j - 1], anc[i + (1 << (j - 1))][j - 1]);
}

stack<int> S;
void dfs()
{
	while (S.size()) S.pop();
	S.push(1);
	memset(pre, 0, sizeof(pre));
	dep[1] = 0;
	memset(fa, -1, sizeof(fa));
	fa[1] = 1;
	dfn = tot = 0;
	memset(vis, 0, sizeof(vis));
	while (S.size())
	{
		int u = S.top();
		if (pre[u])
		{
			post[u] = dfn;
			if (fa[u] > 0) rmq[tot++] = pre[fa[u]];
			S.pop();
			continue;
		}
		pre[u] = ++dfn;
		rmq_pos[u] = tot;
		rmq[tot++] = dfn;
		dfn_to_node[dfn] = u;
		for (int i = 0; i < G[u].size(); ++i)
		{
			int x = G[u][i];
			if (vis[x] || del[x]) continue;
			vis[x] = true;
			Edge&e = edges[x];
			int v = e.u == u ? e.v : e.u;
			if (fa[v] != -1)
			{
				oper[Q].c = 0;
				oper[Q].a = min(u, v);
				oper[Q].b = max(u, v);
				++Q;
			}
			else
			{
				fa[v] = u;
				dep[v] = dep[u] + 1;
				S.push(v);
			}
		}
	}
	seg_tree.init();
	for (int i = 1; i <= N; ++i)
		seg_tree.Update(pre[i], pre[i], dep[i], 1, N, 1);
}

void input()
{
	for (int i = 0; i < M; ++i)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		if (u>v) swap(u, v);
		edges[i] = Edge(u, v);
	}
	sort(edges, edges + M);
	memset(del, 0,  sizeof(del));
	Q = 0;
	int c, a, b;
	while (scanf("%d", &c) == 1)
	{
		if (c == -1) break;
		scanf("%d%d", &a, &b);
		if (a > b) swap(a, b);
		oper[Q++] = Oper(c, a, b);
		if (c == 0)
		{
			int z = lower_bound(edges, edges + M, Edge(a, b)) - edges;
			del[z] = true;
		}
	}
}

void buildtree()
{
	for (int i = 1; i <= N; ++i)
	{
		G[i].clear();
		p[i] = i;
	}
	for (int i = 0; i < M; ++i) if (!del[i])
	{
		int u = edges[i].u, v = edges[i].v;
		G[u].push_back(i);
		G[v].push_back(i);
	}
	dfs();
	make_rmq();
}

int LCA(int u, int v)
{
	u = find(u), v = find(v);
	u = rmq_pos[u], v = rmq_pos[v];
	if (u > v) swap(u, v);
	int k = 0;
	while ((1 << (k + 1)) <= v - u + 1) ++k;
	return dfn_to_node[min(anc[u][k], anc[v - (1 << k) + 1][k])];
}

void Destroy(int u, int rt)
{
	while (u != rt)
	{
		seg_tree.Update(pre[u], post[u], -1, 1, N, 1);
		p[u] = rt;
		u = find(fa[u]);
	}
}

void Update(int u, int v)
{
	u = find(u), v = find(v);
	int lca = find(LCA(u, v));
	Destroy(u, lca);
	Destroy(v, lca);
}

int Query(int u, int v)
{
	u = find(u), v = find(v);
	int lca = find(LCA(u, v));
	int deepu = seg_tree.Query(pre[u], 1, N, 1);
	int deepv = seg_tree.Query(pre[v], 1, N, 1);
	int deeplca = seg_tree.Query(pre[lca], 1, N, 1);
	return deepu + deepv - 2 * deeplca;
}

void solve()
{
	for (int i = Q - 1; i >= 0; --i)
	if (oper[i].c == 0) Update(oper[i].a, oper[i].b);
	else oper[i].ans = Query(oper[i].a, oper[i].b);
	for (int i = 0; i < Q;++i) 
	if (oper[i].c == 1) printf("%d\n", oper[i].ans);
}

int main()
{
//	freopen("intpu.in", "r", stdin);
	while (scanf("%d%d", &N, &M) == 2)
	{
		input();
		buildtree();
		solve();
	}
}

原文链接：https://blog.csdn.net/wsx1754175/article/details/22519417