\(\text{Problem}\)

给定一张无向图，\(q\) 次询问，删去一个点或一条相邻两点间的边，问两点是否连通

询问独立

\(\text{Solution}\)

明显的用圆方树把图变成树

然后问一棵树中删去一个点或一条边两点连不连通

只要讨论点双上的点与边，\(LCA\) 与割去点的位置关系即可

\(\text{Code}\)

#include <cstdio>

#include <iostream>

#include <cstring>

#define RE register

#define IN inline

using namespace std;

const int N = 2e5 + 5;

int n, m, q, cnt, tot1, tot2, top, dfc;

int h1[N], h2[N], dfn[N], low[N], fa[N][21], dep[N], siz[N], stk[N];

struct edge{int nxt, to;}e1[N * 5], e2[N * 5];

IN void add1(int x, int y){e1[++tot1] = edge{h1[x], y}, h1[x] = tot1;}

IN void add2(int x, int y){e2[++tot2] = edge{h2[x], y}, h2[x] = tot2;}

void Tarjan(int x)

{

	stk[++top] = x, low[x] = dfn[x] = ++dfc;

	for(RE int i = h1[x]; i; i = e1[i].nxt)

	{

		int v = e1[i].to;

		if (!dfn[v])

		{

			Tarjan(v), low[x] = min(low[x], low[v]);

			if (dfn[x] == low[v])

			{

				++cnt, add2(cnt, x), add2(x, cnt);

				for(RE int u = 0; u != v; --top) u = stk[top], add2(cnt, u), add2(u, cnt);

			}

		}

		else low[x] = min(low[x] , dfn[v]);

	}

}

void Dfs(int x)

{

	dfn[x] = ++dfc, siz[x] = 1;

	for(RE int i = 1; i <= 18; i++)

		if (fa[x][i - 1]) fa[x][i] = fa[fa[x][i - 1]][i - 1];

		else break;

	for(RE int i = h2[x]; i; i = e2[i].nxt)

	{

		int v = e2[i].to;

		if (v == fa[x][0]) continue;

		dep[v] = dep[x] + 1, fa[v][0] = x, Dfs(v), siz[x] += siz[v];

	}

}

IN int LCA(int x, int y)

{

	int u = x, v = y;

	if (dep[u] < dep[v]) swap(u , v);

	int deep = dep[u] - dep[v];

	for(RE int i = 0; i <= 18; i++) if (deep & (1 << i)) u = fa[u][i];

	if (u == v) return u;

	for(RE int i = 18; i >= 0; i--)

		if (fa[u][i] ^ fa[v][i]) u = fa[u][i], v = fa[v][i];

	return fa[u][0];

}

int main()

{

	scanf("%d%d", &n, &m);

	for(RE int i = 1, x, y; i <= m; i++) scanf("%d%d", &x, &y), add1(x, y), add1(y, x);

	cnt = n, Tarjan(1), dfc = 0, Dfs(1), scanf("%d", &q);

	for(RE int op, x, y, u, v, flag, lca; q; q--)

	{

		scanf("%d%d%d%d", &op, &x, &y, &u), flag = 0;

		if (op == 1)

		{

			scanf("%d", &v), lca = LCA(u, v);

			if (dep[u] < dep[v]) swap(u, v);

			if (lca != u && lca != v) flag = 1;

			else if (siz[fa[u][0]] > siz[u] + 1) flag = 1;

			else{

				lca = LCA(x, y);

				if (dfn[lca] >= dfn[u] && dfn[lca] <= dfn[u] + siz[u] - 1) flag = 1;

				else if (!(dfn[x] >= dfn[u] && dfn[x] <= dfn[u] + siz[u] - 1) && !(dfn[y] >= dfn[u] && dfn[y] <= dfn[u] + siz[u] - 1))

					flag = 1;

			}

		}

		else{

			lca = LCA(x, y);

			if (lca == u);

			else if (dfn[lca] > dfn[u] && dfn[lca] <= dfn[u] + siz[u] - 1) flag = 1;

			else if (!(dfn[x] >= dfn[u] && dfn[x] <= dfn[u] + siz[u] - 1) && !(dfn[y] >= dfn[u] && dfn[y] <= dfn[u] + siz[u] - 1))

				flag = 1;

		}

		if (flag) printf("yes\n"); else printf("no\n");

	}

}

巴特西

JZOJ 2114. 【GDKOI2011】反恐任务

\(\text{Problem}\)

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章