自动搬运

查看原文

来自洛谷，原作者为

	Acerkaio 物以类聚，鸟以群分

搬运于2025-08-24 21:37:27，当前版本为作者最后更新于2023-03-07 20:26:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

易知：此题在同一个边双连通分量中的每一条边都可以走一遍，我们遍可以将一个边双连通分量，缩成一个点，这个点的点权 $w1_i$ 便是该边双连通分量边权和。

缩完之后，我们剩下的边都是割边，便是一颗树，那么 $s$ 到 $t$ 只会有一个简单路径，便是新图的 $col_s$ 到 $col_t$，$col_i$ 是 $i$ 所在的边双中的代表元素，即为 $col_s$ 到 $lca_{col_s, col_t}$ 的边权和加上 $col_t$ 到 $lca_{col_s, col_t}$的边权和，我们可以维护一个从根节点到每个点的边权和 $w2_i$ 那么答案即为

$w2_x + w2_y - 2 \times w2_{lca_{col_s, col_t}} + w1_{lca_{col_s, col_t}}$

CODE:

#include <bits/stdc++.h>
using namespace std;
const int _ = 1e6;

int head[_], tot = 1;
struct NODE {
	int x, y, edge, next;
} edge[_ << 1];

void add(int u, int v, int ed) {
	tot++;
	edge[tot].x = u;
	edge[tot].y = v;
	edge[tot].edge = ed;
	edge[tot].next = head[u];
	head[u] = tot;
}

int head1[_], thoth = 1;
struct ND {
	int x, y, edge, next;
} edge1[_ << 1];


void add1(int u, int v, int ed) {
	thoth++;
	edge1[thoth].x = u;
	edge1[thoth].y = v;
	edge1[thoth].edge = ed;
	edge1[thoth].next = head1[u];
	head1[u] = thoth;
}

int dfn[_], low[_], NOD, cut[_], w1[_], w2[_];
int col[_];
stack <int> lxq;
void Tarjan(int u, int ed) {
	dfn[u] = low[u] = ++NOD;
	lxq.push(u);
	for (int i = head[u], v; v = edge[i].y, i; i = edge[i].next) {
		if (!dfn[v]) {
			Tarjan(v, i);
			if (dfn[u] < low[v]) {
				cut[i] = cut[i ^ 1] = 1;
			}
			low[u] = min(low[u], low[v]);
		} else {
			if (i != (ed ^ 1)) {
				low[u] = min(low[u], dfn[v]);
			}
		}
	}
	if (dfn[u] == low[u]) {
		while (lxq.top() != u) {
			col[lxq.top()] = u;
			lxq.pop();
		}
		col[lxq.top()] = u;
		lxq.pop();
	}
}


/*po*/

int fa[_], Hson[_], Dep[_], Size[_], Top[_], seg[_], rev[_], DFNtot = 0;
void Podfs1(int p, int f, int deg) {
	fa[p] = f;
	Dep[p] = Dep[f] + 1;
	Size[p] = 1;
	w2[p] += w1[p] + deg;
	for (int i = head1[p]; i; i = edge1[i].next) {
		int v = edge1[i].y;
		if (v == f) continue;
		Podfs1(v, p, w2[p] + edge1[i].edge);
		Size[p] += Size[v];
		if (Size[v] > Size[Hson[p]]) Hson[p] = v;
	}
}
void Podfs2(int p, int top) {
	++DFNtot;
	Top[p] = top;
	seg[p] = DFNtot;
	rev[DFNtot] = p;
	if (Hson[p])
		Podfs2(Hson[p], top);
	for (int i = head1[p]; i; i = edge1[i].next) {
		int v = edge1[i].y;
		if (v == fa[p]) continue;
		if (Hson[p] != v) Podfs2(v, v);
	}
}

int LCA(int u, int v) {

	int fu = Top[u], fv = Top[v];
	while (fu != fv) {
//		cout << u << ' ' << v << '\n';
		if (Dep[fu] < Dep[fv]) swap(fu,fv), swap(u, v);
		u = fa[fu], fu = Top[u];
	}
	return Dep[u] < Dep[v] ? u : v;
}
signed main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);
		add(y, x, z);
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i]) Tarjan(i, 0);
	for (int i = 1; i <= tot; i++) {
		int u = col[edge[i].x], v = col[edge[i].y], w = edge[i].edge;
		if (u == v) {
			w1[u] += w;
		} else {
			add1(u, v, w);
		}
	}
	
	Podfs1(1, 1, 0);
	Podfs2(1, 1);
	int q;
	cin >> q;
	
	for (int i = 1; i <= q; i++) {
		int x, y, lca;
		cin >> x >> y;
		//cout << x << ' ' << y << '\n'; 
		x = col[x], y = col[y];
//		cout << x << ' ' << y;
		lca = LCA(x, y);
		if (w2[x] + w2[y] - 2 * w2[lca] + w1[lca] > 0) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}