题意：有一个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
*/
京公网安备 11010502036488号