题解：P11644 【MX-X8-T3】「TAOI-3」地地爱打卡

szh_AK_all · 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";
    }
}