hdu 5458 Stability （并查集+线段树+树链剖分（边权））

题意：有一个n个点m条边的图，有q次操作，操作1删掉一条a b之间的边，操作2询问a  b之间的必要边，必要边指的是，从a到b必须要经过的边。（题目说明了：在任何情况下，保证整个图的连通）

思路：

1、如果要直接计算图中两点联通的必要边的话，显然不太可行

2、那我们把完成所有操作后的图看成一棵树，和几条边，那么对应的操作就变成了加边和询问

3、树上任意两点保证有且只有一条路径，并且如果对于树询问必要边的话，就是路径上的边数

4、对于操作1，我们给树上两点加上一条路径，就意味着这两个点和他们路径上的点，这些点之间的任意两点可以通过两条路到达，即没有必要边，所以对于操作1，我们只需要将两点之间的路径的权值全部改为 0 就可以。

5、对于操作2，我们只需要查询一下两点在树上的距离就可以。

6、整合一下，整个题目就变成了，先求出最后的图，并且将最后的图变成一棵树加上若干条边，对于若干条边，用操作1将这些边的两个端点之间的距离设为0，反向询问，对于操作1，将这两个点之间的距离设为0，对于操作2，查询这两点在树上的距离，

7、所以大概就是     并查集+线段树+树链剖分（边权） https://blog.csdn.net/qq_41608020/article/details/89766333

8、对于将一个图变成一棵树和若干条边我们可以用并查集来操作

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
const ll MAXN = 100005;
struct edge
{
	int to;
	int nex;
}e[MAXN * 2];
int head[MAXN], tot;
int n, m, q;
int fa[MAXN], son[MAXN], deep[MAXN], num[MAXN];
int top[MAXN], p[MAXN], fp[MAXN];
int pos;
int ql, qr;
ll val;
void init()
{
	tot = 0;
	memset(head, -1, sizeof(head));
	pos = 1;
	memset(son, -1, sizeof(son));
}
void add(int a, int b)
{
	e[tot] = edge{ b,head[a] };
	head[a] = tot++;
}
void dfs1(int u, int pre, int dep)
{
	deep[u] = dep;
	fa[u] = pre;
	num[u] = 1;
	for (int i = head[u]; i + 1; i = e[i].nex)
	{
		int v = e[i].to;
		if (v != pre)
		{
			dfs1(v, u, dep + 1);
			num[u] += num[v];
			if (son[u] == -1 || num[son[u]] < num[v])
				son[u] = v;
		}
	}
}
void dfs2(int u, int sp)
{
	top[u] = sp;
	p[u] = pos++;
	fp[p[u]] = u;
	if (son[u] == -1)
		return;
	dfs2(son[u], sp);
	for (int i = head[u]; i + 1; i = e[i].nex)
	{
		int v = e[i].to;
		if (v != son[u] && v != fa[u])
			dfs2(v, v);
	}
}

struct node
{
	int l;
	int r;
	ll sum;
	int mark;
}que[MAXN * 4];
void up(int k)
{
	que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
}
void down(int k)
{
	if (que[k].mark)
	{
		que[k << 1].mark = que[k].mark;
		que[k << 1 | 1].mark = que[k].mark;
		que[k << 1].sum = 0;
		que[k << 1 | 1].sum = 0;
		que[k].mark = 0;
	}
}
void build(int left = 1, int right = pos, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = 0;
	if (left == right)
		return;
	imid;
	build(lson);
	build(rson);
}
void update(int left = 1, int right = pos, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		if (val == 0)
		{
			que[k].mark = 1;
			que[k].sum = 0;
		}
		else
		{
			que[k].sum = 1;
		}
		return;
	}
	down(k);
	imid;
	update(lson);
	update(rson);
	up(k);
}
ll query(int left = 1, int right = pos, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].sum;
	down(k);
	imid;
	return query(lson) + query(rson);
}

void change(int u, int v)
{
	int f1 = top[u], f2 = top[v];
	while (f1 != f2)
	{
		if (deep[f1] < deep[f2])
		{
			swap(f1, f2);
			swap(u, v);
		}
		ql = p[f1];
		qr = p[u];
		val = 0;
		update();
		u = fa[f1];
		f1 = top[u];
	}
	if (u == v)
		return;
	if (deep[u] > deep[v])
		swap(u, v);
	ql = p[son[u]];
	qr = p[v];
	val = 0;
	update();
}

ll changes(int u, int v)
{
	ll res = 0;
	int f1 = top[u], f2 = top[v];
	while (f1 != f2)
	{
		if (deep[f1] < deep[f2])
		{
			swap(f1, f2);
			swap(u, v);
		}
		ql = p[f1];
		qr = p[u];
		res += query();
		u = fa[f1];
		f1 = top[u];
	}
	if (u == v)
		return res;
	if (deep[u] > deep[v])
		swap(u, v);
	ql = p[son[u]];
	qr = p[v];
	res += query();
	return res;
}

#define Pair pair<int,int>
int in[MAXN][3];
int op[MAXN][3];
int ques[MAXN];
int preop[MAXN][2];
int qq;

void initbcj()
{
	qq = 0;
	for (int i = 1; i <= n; i++)
		ques[i] = i;
}
int getf(int k)
{
	return ques[k] == k ? k : ques[k] = getf(ques[k]);
}
void merge(int a, int b)
{
	ques[getf(a)] = getf(b);
}

int main()
{
	int T, cas = 1;
	scanf("%d", &T);
	while (T--)
	{
		map<Pair, int>mp;
		vector<ll>ans;
		scanf("%d%d%d", &n, &m, &q);
		init();
		initbcj();
		for (int i = 0; i < m; i++)
		{
			scanf("%d%d", &in[i][0], &in[i][1]);
			if (in[i][0] > in[i][1])
				swap(in[i][0], in[i][1]);
			mp[Pair{ in[i][0],in[i][1] }]++;
			//add(in[i][0], in[i][1]);
			//add(in[i][1], in[i][0]);
		}
		for (int i = 0; i < q; i++)
		{
			scanf("%d%d%d", &op[i][0], &op[i][1], &op[i][2]);
			if (op[i][1] > op[i][2])
				swap(op[i][1], op[i][2]);
			if (op[i][0] == 1)
				mp[Pair{ op[i][1],op[i][2] }]--;
		}

		//重新做边
		m = 0;
		for (auto it = mp.begin(); it != mp.end(); it++)
		{
			if (it->second != 0)
			{
				int q = getf(it->first.first), w = getf(it->first.second);
				if (q != w)//树
				{
					add(it->first.first, it->first.second);
					add(it->first.second, it->first.first);
					in[m][0] = it->first.first;
					in[m][1] = it->first.second;
					in[m][2] = it->second;
					m++;
					merge(it->first.first, it->first.second);
				}
				else//若干条边
				{
					preop[qq][0] = it->first.first;
					preop[qq][1] = it->first.second;
					qq++;
				}
			}
		}

		dfs1(1, 0, 0);
		dfs2(1, 1);
		build();
		for (int i = 0; i < m; i++)
		{
			if (deep[in[i][0]] > deep[in[i][1]])
				swap(in[i][0], in[i][1]);
			ql = p[in[i][1]];
			qr = ql;
			val = in[i][2];
            //如果是重边和自环就没有必要边
			if (val > 1 || in[i][0] == in[i][1])
				val = 0;
			update();
		}

		//preop set 0   若干条边
		for (int i = 0; i < qq; i++)
			change(preop[i][0], preop[i][1]);

		for (int i = q - 1; i >= 0; i--)
		{
			if (op[i][0] == 1)
			{
				ql = op[i][1];
				qr = op[i][2];
				change(ql, qr);
			}
			else
			{
				ql = op[i][1];
				qr = op[i][2];
				ll res = changes(ql, qr);
				ans.push_back(res);
			}
		}
		printf("Case #%d:\n", cas++);
		int len = ans.size();
		for (int i = len - 1; i >= 0; i--)
		{
			printf("%lld\n", ans[i]);
		}
	}
}
/*
1
5 6 5
1 2
1 4
2 4
2 3
4 5
2 4
2 2 4
2 1 4
1 1 2
2 2 4
2 1 2

*/