Znzryb's Blog

P4391 [BalticOI 2009] Radio Transmission 无线传输

Posted on 2025-06-25 Edited on 2026-03-02

题目内容

题目描述

给你一个字符串 $s_1$ ，它是由某个字符串 $s_2$ 不断自我连接形成的（保证至少重复 $2$ 次）。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行一个整数 $L$ ，表示给出字符串的长度。

第二行给出字符串 $s_1$ 的一个子串，全由小写字母组成。

输出格式

仅一行，表示 $s_2$ 的最短长度。

输入输出样例 #1

输入 #1

1 2	8 cabcabca

输出 #1

说明/提示

样例输入输出 1 解释

对于样例，我们可以利用 $\texttt{abc}$ 不断自我连接得到 $\texttt{abcabcabcabc}$ ，读入的 $\texttt{cabcabca}$ ，是它的子串。

规模与约定

对于全部的测试点，保证 $1\le L \le 10^6$ 。

思路讲解

给出子串，找出最短循环节。

最大公共前后缀。

结论就是N-pi[N]。~~其实我也不是很懂。~~

不能够使用二分，因为周期并没有单调性。

这道题目 hash 怎么做？

哈希做法思路

核心观察：字符串 $s$ 的最小周期为 $p$ ，当且仅当 $p$ 是满足以下条件的最小正整数：

s_i = s_{i+p} \quad \forall\, 0 \le i < L - p

这等价于： $s$ 去掉前 $p$ 个字符得到的后缀，与去掉后 $p$ 个字符得到的前缀完全相同。即：

s[0 \ldots L-p-1] = s[p \ldots L-1]

用多项式哈希预处理后，每次子串比较 $O(1)$ 。从 $p=1$ 开始枚举，第一个满足条件的 $p$ 就是答案。总复杂度 $O(L)$ 。
参考代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;

    const long long MOD1 = 1e9 + 7, BASE1 = 131;
    const long long MOD2 = 1e9 + 9, BASE2 = 137;

    vector<long long> h1(n + 1), h2(n + 1), pw1(n + 1), pw2(n + 1);
    h1[0] = h2[0] = 0;
    pw1[0] = pw2[0] = 1;
    for (int i = 0; i < n; i++) {
        h1[i + 1] = (h1[i] * BASE1 + s[i]) % MOD1;
        h2[i + 1] = (h2[i] * BASE2 + s[i]) % MOD2;
        pw1[i + 1] = pw1[i] * BASE1 % MOD1;
        pw2[i + 1] = pw2[i] * BASE2 % MOD2;
    }

    auto qry = [&](int l, int r) -> pair<long long, long long> {
        long long v1 = (h1[r + 1] - h1[l] * pw1[r - l + 1] % MOD1 + MOD1 * 2) % MOD1;
        long long v2 = (h2[r + 1] - h2[l] * pw2[r - l + 1] % MOD2 + MOD2 * 2) % MOD2;
        return {v1, v2};
    };

    for (int p = 1; p <= n; p++) {
        if (qry(0, n - p - 1) == qry(p, n - 1)) {
            cout << p << '\\n';
            return 0;
        }
    }
}

用了双哈希避免冲突。本质上和 KMP 中 $L - \pi_L$ 的经典做法等价，只是换了一种判断周期的手段。

详细解释关键观察

这其实就是把逐字符的条件"打包"成了一个子串相等的条件，是同一件事的两种说法。
逐字符展开：两个长度相同的子串相等，就是对应位置的字符全部相等。把两个子串的对应位置写出来：

前缀中的第 $i$ 个字符	后缀中的第 $i$ 个字符
$s[0]$	$s[p]$
$s[1]$	$s[p+1]$
$\vdots$	$\vdots$
$s[i]$	$s[i+p]$
$\vdots$	$\vdots$
$s[L-p-1]$	$s[L-1]$
前缀的第 $i$ 个字符是 $s[i]$ ，后缀的第 $i$ 个字符是 $s[i+p]$ 。
所以"两个子串相等" $\iff$ 每一行都对应相等 $\iff$ $s_i = s_{i+p}$ 对所有 $0 \le i < L-p$ 成立。
用例子直观感受：取 `cabcabca`， $p = 3$ ：

前缀（去掉后3个）：c a b c a
后缀（去掉前3个）：c a b c a
                    ↕ ↕ ↕ ↕ ↕
原串位置对应：     s[0]=s[3], s[1]=s[4], s[2]=s[5], s[3]=s[6], s[4]=s[7]

每个字符都和它后面第 $p$ 个字符相同，这就是"周期为 $p$ "的含义。把这些逐个比较合在一起看，就是前缀和后缀相等。
两种说法完全等价，只是视角不同：一个是逐字符看，一个是整体看。

把这个列出来以后，我们就知道了周期 p 的成立条件是什么。可以通过枚举 p，非常简单的使用字符串哈希检验答案。

AC代码

https://www.luogu.com.cn/record/221541535

源代码

// Problem: P4391 [BalticOI 2009] Radio Transmission 无线传输
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4391
// Memory Limit: 125 MB
// Time Limit: 1000 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(){
	
}

inline void solve(){
	cin>>N;
	init();
	string s;
	cin>>s;
	// if(N==1) {cout<<1<<"\n";return;}
	s='#'+s;
	vector<ll> pi(N+5);
	FOR(i,1,N){
		if(i==1) continue;
		ll len=pi[i-1];
		while(true){
			if(s[i]==s[len+1]){
				pi[i]=len+1;
				break;
			}
			if(len==0) break;
			len=pi[len];
		}
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<pi[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	// ll ans=0;
	// FOR(i,1,N){
		// ans=max(ans,pi[i]);
	// }
	cout<<N-pi[N]<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/221541535
*/

心路历程（WA，TLE，MLE……）

P3375 【模板】KMP（前缀函数）（完全理解 kmp）

Posted on 2025-06-25 Edited on 2026-03-23

思路讲解

https://cp-algorithms.com/string/prefix-function.html

【KMP 学一遍忘一遍？ACM 金牌选手用可视化直击本质，理解了内核后想忘记都难！】【精准空降到 04:05】 https://www.bilibili.com/video/BV1Er421K7kF/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=245

那么我们容易发现，这个

ABC……ABC+D，那么如果前缀字符串后面跟着D，那么就是pi函数=4，但是如果后面不是D，那要怎么办？

不难发现， $S[i+1]=S[\pi[i]+1] \Rightarrow\pi[i+1]=\pi[i]+1$ （注意，这里我采用的是1-based，这更自然）。这不言而喻。（上面的这个图片已经解释了，我们再细化一下）

当然，这个是皆大欢喜的情况，但是如果出现失配了怎么办？

这个 pi_next()，为什么一定是这个 pi_next()。可以使用反证法。

okay，问题就来到了，怎么样使用前缀数组实现这个文本串和模式串的这个匹配？

//                  文本串             模式串
vector<ll> kmp(const string &s1,const string &s2){	// 返回总前缀数组pi
	string S;
	S='#'+s2+'#'+s1;		// 采用1-based 
	N=SZ(S)-1;
	vector<ll> pi(N+1,0);
	FOR(i,1,N){
		if(i==1) continue;
		ll len=pi[i-1];
		// if(S[i]==S[len+1]){
			// pi[i]=len+1;
		// }
		while(true){
			if(S[i]==S[len+1]){
				 pi[i]=len+1;
				 break;
			}
			if(len==0) break;
			len=pi[len];
		}
	}
	return pi;
}

特别的，我们认为 i=1 的时候 pi[i]=0。


/*
 * 采用 0-based 设计
 * 模式串(s2)+'#'+文本串(s1) 需要这样子传入，如果想要执行 kmp 的话
 * kmp 模板题 AC https://www.luogu.com.cn/record/269142391
 */
vector<ll> kmp(const string &A) {
    // 返回总前缀数组pi
    // 其定义是【1；i】真前后缀相同的最长长度
    // 特别的，pi【1】=0
    vector<ll> pi(SZ(A));
    for (int i = 1; i < SZ(A); ++i) {
        ll len = pi[i - 1];
        while (len > 0 && A[len] != A[i]) {
            len = pi[len - 1];
        }
        if (A[len] == A[i]) {
            pi[i] = len + 1;
        }
    }
    return pi;
}

void Solve() {
    string s1, s2;
    cin >> s1 >> s2;
    vector<ll> pi = kmp(s2 + "#" + s1);
    for (int i = SZ(s2); i < SZ(pi); ++i) {
        if (pi[i] == SZ(s2)) {
            ll ans = i - SZ(s2) - SZ(s2);
            ++ans;
            cout << ans << "\n";
        }
    }
    for (int i = 0; i < SZ(s2); ++i) {
        cout << pi[i] << " ";
    }
    cout << "\n";
}

AC代码

源代码

// Problem: P3375 【模板】KMP
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3375
// Memory Limit: 512 MB
// Time Limit: 1000 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> kmp(const string &s1,const string &s2){	// 返回总前缀数组pi
	string S;
	S='#'+s2+'#'+s1;		// 采用1-based 
	N=SZ(S)-1;
	vector<ll> pi(N+1,0);
	FOR(i,1,N){
		if(i==1) continue;
		ll len=pi[i-1];
		while(true){
			if(S[i]==S[len+1]){
				 pi[i]=len+1;
				 break;
			}
			if(len==0) break;
			len=pi[len];
		}
	}
	return pi;
}
inline void solve(){
	string s,s1;
	cin>>s>>s1;
	init();
	vector<ll> pi=kmp(s,s1);
#ifdef LOCAL
   FOR(i,1,N){
   		debug(i);
		debug(pi[i]);
	}
#endif
	FOR(i,1,SZ(pi)-1){
		if(pi[i]==SZ(s1)){
			cout<<i-SZ(s1)*2<<"\n";
		}
	}
	FOR(i,1,SZ(s1)){
		cout<<pi[i]<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/221413997
*/

AC
https://www.luogu.com.cn/record/269142391

源代码

/**
 * Problem: P3375 【模板】KMP
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P3375
 * Created: 2026-03-23 13:08:20
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

/*
 * 采用 0-based 设计
 * 模式串(s2)+'#'+文本串(s1) 需要这样子传入，如果想要执行 kmp 的话
 * kmp 模板题 AC https://www.luogu.com.cn/record/269142391
 */
vector<ll> kmp(const string &A) {
    // 返回总前缀数组pi
    // 其定义是【1；i】真前后缀相同的最长长度
    // 特别的，pi【1】=0
    vector<ll> pi(SZ(A));
    for (int i = 1; i < SZ(A); ++i) {
        ll len = pi[i - 1];
        while (len > 0 && A[len] != A[i]) {
            len = pi[len - 1];
        }
        if (A[len] == A[i]) {
            pi[i] = len + 1;
        }
    }
    return pi;
}

void Solve() {
    string s1, s2;
    cin >> s1 >> s2;
    vector<ll> pi = kmp(s2 + "#" + s1);
    for (int i = SZ(s2); i < SZ(pi); ++i) {
        if (pi[i] == SZ(s2)) {
            ll ans = i - SZ(s2) - SZ(s2);
            ++ans;
            cout << ans << "\n";
        }
    }
    for (int i = 0; i < SZ(s2); ++i) {
        cout << pi[i] << " ";
    }
    cout << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
    Solve();
    return 0;
}

/*

*/

心路历程（WA，TLE，MLE……）

P11643 【MX-X8-T2】「TAOI-3」终有一天，飞向水平线的彼方（区间操作化简）

Posted on 2025-06-25 Edited on 2026-02-17

思路讲解

那么容易发现，其实这种区间操作的题目一般来说最短的操作是最灵活的，一个长操作也可以化为多个短操作的结果。

比如说这道题目长度为4的操作可以变为对中间两个元素执行一次，再对两侧两个元素分别执行一次。

所以我们不用考虑长度>2的操作。

那么不难注意到，就是说这个开头和结尾往往是这个破局的地方，那么开头那如果不同，必须要操作后面一个，然后不断传递，最后传递到A_[N]，就结束了。

FOR(i,1,N){
	cin>>A[i];
	A_[i]=A[i];
}
FOR(i,1,N){
	cin>>B[i];
}
FOR(i,1,N-1){
	ll diff=B[i]-A_[i];
	A_[i+1]+=diff;
}
if(A_[N]==B[N]){
	cout<<"Yes\n";
}else{
	cout<<"No\n";
}

AC代码

https://www.luogu.com.cn/record/221383853

源代码

// Problem: P11643 【MX-X8-T2】「TAOI-3」终有一天，飞向水平线的彼方
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11643
// 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],B[MAXN];
ll A_[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>A[i];
		A_[i]=A[i];
	}
	FOR(i,1,N){
		cin>>B[i];
	}
	FOR(i,1,N-1){
		ll diff=B[i]-A_[i];
		A_[i+1]+=diff;
	}
	if(A_[N]==B[N]){
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

Starter 190-1-2 Reorder

Posted on 2025-06-25 Edited on 2026-02-17

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）

P11644 【MX-X8-T3】「TAOI-3」地地爱打卡（注意特判奇数环和独立点）

Posted on 2025-06-24 Edited on 2026-03-17

思路讲解

由于奇数环既有一条偶数路径，又有一条奇数路径，可以直接特判。

重要程序解析

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

源代码

// 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

*/