P11644 【MX-X8-T3】「TAOI-3」地地爱打卡（注意特判奇数环和独立点） · znzryb
## 思路讲解
由于奇数环既有一条偶数路径，又有一条奇数路径，可以直接特判。
::: 重要程序解析
```cpp
auto dfs=[&](auto &&dfs,ll u,ll col,ll fa)->void{
vis[u]=true;
color[u]=col;
FOR(i,0,SZ(g[u])-1){
ll v=g[u][i];
if(v==fa) continue;
if(vis[v]){
ll diff=col-color[v]; // 判奇数环可以使用这种方式
if(diff%2==0){
isji[dsu.find(v)]=true;
}
continue;
}
dfs(dfs,v,1+col,u);
}
};
FOR(i,1,N){
if(vis[i]){
continue;
}
dfs(dfs,i,1,0);
}
FOR(i,1,Q){
ll s,t,x;
cin>>s>>t>>x;
if(dsu.same(s,t)==false){
cout<<"expand\n";
continue;
}
if(dsu.size(s)==1 && x!=0){ // 对独立点的特判
cout<<"expand\n";
continue;
}
if(isji[dsu.find(s)]){
cout<<"tribool\n";
continue;
}
ll diff=abs(color[s]-color[t]);
if(diff%2==1 && x%2==1){
cout<<"tribool\n";
continue;
}
if(diff%2==0 && x%2==0){
cout<<"tribool\n";
continue;
}
cout<<"expand\n";
}
```
:::
## AC代码
[https://www.luogu.com.cn/record/221314756](https://www.luogu.com.cn/record/221314756)
::: 源代码
```cpp
// Problem: D - 「TAOI-3」地地爱打卡
// Contest: Virtual Judge - 20250624暑假训练
// URL: https://vjudge.net/contest/724839#problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT,A[MAXN];
/*
*/
inline void init(){
}
vector<ll> g[MAXN]; // 记得要清空
struct DSU { // 并查集
vector < int > fa, siz;
int ln;
DSU(int n) {
ln = n;
fa.resize(ln + 5, 0), siz.resize(ln + 5, 0);
FOR(i, 1, n) {
fa[i] = i;
siz[i] = 1;
}
}
int find(int x) {
while (fa[x] != x) {
x = fa[x];
fa[x] = fa[fa[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
fa[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
int countFa() {
int res = 0;
FOR(i, 1, ln) {
if (fa[i] == i) ++res;
}
return res;
}
};
inline void solve(){
cin>>N>>M>>Q;
init();
DSU dsu(N);
FOR(i,1,M){
ll u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
dsu.merge(u,v);
}
vector<bool> vis(N+5,false);
vector<ll> color(N+5,0);
vector<bool> isji(N+5,false);
auto dfs=[&](auto &&dfs,ll u,ll col,ll fa)->void{
vis[u]=true;
color[u]=col;
FOR(i,0,SZ(g[u])-1){
ll v=g[u][i];
if(v==fa) continue;
if(vis[v]){
ll diff=col-color[v];
if(diff%2==0){
isji[dsu.find(v)]=true;
}
continue;
}
dfs(dfs,v,1+col,u);
}
};
#ifdef LOCAL
cerr << "OK" << '\n';
#endif
FOR(i,1,N){
if(vis[i]){
continue;
}
dfs(dfs,i,1,0);
#ifdef LOCAL
debug(i);
#endif
}
#ifdef LOCAL
cerr << "OK" << '\n';
FOR(i,1,N){
cerr<<color[i]<<" ";
}
cerr<<"\n";
FOR(i,1,N){
cerr<<isji[dsu.find(i)]<<" ";
}
#endif
FOR(i,1,Q){
ll s,t,x;
cin>>s>>t>>x;
if(dsu.same(s,t)==false){
cout<<"expand\n";
continue;
}
if(dsu.size(s)==1 && x!=0){
cout<<"expand\n";
continue;
}
if(isji[dsu.find(s)]){
cout<<"tribool\n";
continue;
}
ll diff=abs(color[s]-color[t]);
if(diff%2==1 && x%2==1){
cout<<"tribool\n";
continue;
}
if(diff%2==0 && x%2==0){
cout<<"tribool\n";
continue;
}
cout<<"expand\n";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--){
// solve();
// }
solve();
return 0;
}
/*
tribool
*/
```
:::
## 心路历程（WA，TLE，MLE……）