自动搬运

查看原文

来自洛谷，原作者为

	szh_AK_all S挂分挂到被洛谷7级勾卡线|I can do all things

搬运于2025-08-24 23:09:06，当前版本为作者最后更新于2025-01-31 19:16:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

特判有点恶心。

分析

结论：如果 $x$ 和路径长度的奇偶性相同或是在 $s,t$ 所在联通快中含有一个奇环则合法。

证明：因为可以在一条路上来回走，所以可以将快乐值凑到 $x$，由于一个数异或偶数个 $1$ 还是这个数本身，所以最终的能量值也可以凑到 $0$。又因为奇数长度的环可以改变路径长度的奇偶性，所以如果图中有奇环那么一定合法。

做两遍 dfs 即可，第一遍 dfs 判断连通性，第二遍 dfs 找奇环，注意特判孤立点。

#include <bits/stdc++.h>
using namespace std;
vector<int>g[200005];
int shu[200005], vis[200005], cnt;
int vi[200005], dis[200005], ji[200005];

void dfs(int x) {
	if (vis[x])
		return;
	vis[x] = 1;
	for (int y : g[x]) {
		shu[y] = cnt;
		dfs(y);
	}
}

void df(int x, int fa) {
	vi[x] = 1;
	for (int y : g[x]) {
		if (y == fa)
			continue;
		if (!vi[y])
			dis[y] = dis[x] + 1, df(y, x);
		else if (abs(dis[x] - dis[y]) % 2 == 0)
			ji[shu[x]] = 1;
	}
}

int main() {
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
		if (!vis[i])
			shu[i] = ++cnt, dfs(i), df(i, 0);
	while (q--) {
		int s, t, x;
		cin >> s >> t >> x;
		if (shu[s] != shu[t])
			cout << "expand";
		else if (s == t && g[s].size() == 0 && x != 0)
			cout << "expand";
		else {
			if (abs(dis[s] - dis[t]) % 2 == x % 2 || ji[shu[s]])
				cout << "tribool";
			else
				cout << "expand";
		}
		cout << "\n";
	}
}