1002. 希望灯塔

• 数论number_theory
• 递归recursion
• 算术arithmetic

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

#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

struct Node {
	ll p, q;

	bool operator < (const Node &a) const {
		return p * a.q < a.p * q;
	}

	bool operator >= (const Node &a) const {
		return !(*this < a);
	}
};

pair<ll, ll> simplest(ll a, ll b, ll c, ll d) {
	ll x = a / b, y = c / d;

	if (x < y) return {(a + b - 1) / b, 1};
	if (a % b == 0) return {x, 1};

	auto [p, q] = simplest(d, c - x * d, b, a - x * b);
	return {x * p + q, p};
}

void solve() {
	int n, m;
	cin >> n >> m;

	vector<Node> a(n + 1);

	for (int i = 1; i <= n; i ++) cin >> a[i].p;
	for (int i = 1; i <= n; i ++) cin >> a[i].q;

	int cnt1 = 0;

	for (int i = 1; i <= n; i ++) if (a[i].p >= a[i].q) cnt1 ++;

	a[0].q = 1;
	int mx1 = 0, mx2 = 0;

	for (int i = 1; i <= n; i ++) {
		if (a[i] >= a[mx1]) {
			mx2 = mx1;
			mx1 = i;
		} else if (a[i] >= a[mx2]) {
			mx2 = i;
		}
	}

	bool valid = a[mx1].p * a[mx2].p >= a[mx1].q * a[mx2].q;

	ll lim = 0;

	if (cnt1 == 1 && valid) {
		auto [p, q] = simplest(
			a[mx2].q, a[mx2].p,
			a[mx1].p, a[mx1].q
		);
		lim = q;
	}

	while (m --) {
		int pos;
		ll x;
		cin >> pos >> x;

		if (cnt1 >= 2) {
			cout << (a[pos].p * x >= a[pos].q ? "Yes\n" : "No\n");
		} else if (cnt1 == 0 || !valid) {
			cout << "No\n";
		} else {
			ll y;

			if (pos == mx1) y = x;
			else y = a[pos].p * x / a[pos].q;
			cout << (y >= lim ? "Yes\n" : "No\n");
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while (t --) solve();
}

1003. 括号凸包

• 几何geometry
• 凸包convex_hull
• 极角排序angle_sorting
• 动态规划dp

#include<bits/stdc++.h>
#define int long long
#define mx 510
using namespace std;

int mod = 998244353;

struct node{
    int x;
    int y;
    int t;
};

node a[mx];
vector<int>ord[mx];
int rk[mx][mx];
int lim[mx][mx];
int dp[mx][mx];

int w[mx];
int pre[mx];

int now;

int cross(int o,int x,int y){
    return (a[x].x - a[o].x) * (a[y].y - a[o].y)
         - (a[x].y - a[o].y) * (a[y].x - a[o].x);
}

int half(int o,int x){
    int dx = a[x].x - a[o].x;
    int dy = a[x].y - a[o].y;

    if(dy > 0 || (dy == 0 && dx > 0))return 0;
    return 1;
}

bool cmp(int x,int y){
    int hx = half(now,x);
    int hy = half(now,y);

    if(hx != hy)return hx < hy;

    return cross(now,x,y) > 0;
}

bool cmp1(node x,node y){
    if(x.y != y.y)return x.y < y.y;
    return x.x < y.x;
}

void solve(){
    int n;
    cin>>n;

    for(int i = 0;i < n;i++){
        cin>>a[i].x>>a[i].y>>a[i].t;
    }

    sort(a,a + n,cmp1);

    for(int p = 0;p < n;p++){
        ord[p].clear();

        for(int i = 0;i < n;i++){
            if(i != p){
                ord[p].push_back(i);
            }
        }

        now = p;
        sort(ord[p].begin(),ord[p].end(),cmp);
        int m = n - 1;
        for(int i = 0;i < m;i++){
            rk[p][ord[p][i]] = i;
        }

        int q = 1;

        for(int i = 0;i < m;i++){
            q = max(q,i + 1);

            while(q < i + m &&
                  cross(p,ord[p][i],ord[p][q % m]) > 0){
                q++;
            }

            lim[p][i] = q;
        }
    }

    int ans = 0;
    int m = n - 1;

    for(int s = 0;s < n;s++){
        memset(dp,0,sizeof(dp));

        vector<int>v;

        for(int x:ord[s]){
            if(x > s){
                v.push_back(x);
            }
        }

        for(int x:v){
            if(a[s].t != a[x].t){
                dp[s][x] = 1;
            }
        }

        for(int ii = 0;ii < v.size();ii++){
            int i = v[ii];

            fill(w,w + m,0);

            w[rk[i][s]] = dp[s][i];

            for(int hh = 0;hh < ii;hh++){
                int h = v[hh];
                w[rk[i][h]] = dp[h][i];
            }

            pre[0] = 0;

            for(int k = 0;k < m;k++){
                pre[k + 1] = (pre[k] + w[k]) % mod;
            }

            for(int jj = ii + 1;jj < v.size();jj++){
                int j = v[jj];

                if(a[i].t == a[j].t)continue;

                int r = rk[i][j];
                int e = lim[i][r];

                int val = 0;

                if(e <= m){
                    val = pre[e] - pre[r + 1];
                }else{
                    val = pre[m] - pre[r + 1];
                    val += pre[e - m];
                }

                val %= mod;

                if(val < 0)val += mod;

                dp[i][j] = val;

                if(a[j].t != a[s].t && cross(i,j,s) > 0){
                    ans += val;
                    ans %= mod;
                }
            }
        }
    }

    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int T;
    cin>>T;

    while(T--){
        solve();
    }

    return 0;
}

1004. 探索宝物

• 概率论probability
• 前缀和prefix_sum
• 快速幂exponentiation_by_squaring

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'

const int mod = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 5;

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

pii calc(int q, int n) {
    if (n == 0)
        return {1, 0};

    auto [p, sum] = calc(q, n >> 1);
    int np = p * p % mod;
    int ns = sum * (1 + p) % mod;
    if (n & 1) {
        ns = (ns + np) % mod;
        np = np * q % mod;
    }
    return {np, ns};
}

void init() {}

void solve() {
    int n, m, c;
    cin >> n >> m >> c;
    vi w(m);
    for (int i = 0; i < m; i++) cin >> w[i];
    int W = accumulate(all(w), 0LL);
    vi prww(m + 1), prew(m + 1);
    i128 d = 0;
    for (int i = 0; i < m; i++) {
        prww[i + 1] = (prww[i] + w[i]) % mod;
        prew[i + 1] = (prew[i] + (i + 1) % mod * (w[i] % mod)) % mod;
        d += (i128)(i + 1) * w[i];
    }
    int K = m;
    i128 suf = W;
    i128 cost = (i128)c * W;
    for (int x = 0; x <= m; x++) {
        if (d <= cost) {
            K = x;
            break;
        }
        if (x < m) {
            d -= suf;
            suf -= w[x];
        }
    }
    if (K == 0) {
        cout << 0 << endl;
        return;
    }
    int inw = qpow(W % mod, mod - 2);
    int q = prww[K - 1] * inw % mod;
    int tv = (prew[m] - prew[K - 1] + mod) % mod;
    int R = tv * inw % mod;
    auto [qn, geo] = calc(q, n);
    int smd = 0;
    for (int x = 1; x <= K - 2; x++) {
        int fw =prww[x] * inw % mod;
        smd =(smd + qpow(fw, n)) % mod;
    }
    int ans =(R - c % mod + mod) % mod * geo % mod;
    ans =(ans + (K - 1) % mod * qn) % mod;
    ans =(ans - smd + mod) % mod;
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    cin >> t;

    while (t--) solve();

    return 0;
}

1005. indigo 究竟是谁？

• 字符串string
• 树结构集合与映射tree_set
• 模拟simulation

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

void solve() {
	int n, k, m, q;
	cin >> n >> k >> m >> q;

	vector<int> rm(n + 1), sub(n + 1), cnt(n + 1), first(n + 1, 1e9), ans;
	map<string, int> mp;
	int id = 0;

	int last = 0;
	int t = 0;

	for (int i = 1; i <= n; i ++) {
		string s;
		cin >> s;

		int u;
		if (mp[s]) u = mp[s];
		else {
			mp[s] = ++id;
			u = id;
		}

		if (u == last) t ++;
		else {
			last = u;
			t = 1;
		}

		if (rm[u]) {
			last = 0;
			t = 0;
			continue;
		}

		if (i - first[u] - 1 >= m && sub[u] >= k) ans.push_back(i);
		first[u] = min(first[u], i);
		sub[u] = max(sub[u], t);
		cnt[u] ++;
		if (cnt[u] >= q) rm[u] = 1;
	}

	if (ans.empty()) cout << "empty\n";
	else {
		for (auto i : ans) cout << i << ' ';
		cout << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	//freopen("in.txt", "r", stdin);

	int t;
	cin >> t;
	while (t --) solve();
}

1006. 三串共鸣

• Z 函数z
• 字符串string
• 数据结构data_structures

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 17;
void init() {}
struct BIT {
    int n;
    vi t;
    BIT() {}
    BIT(int n):n(n),t(n+1){}
    void add(int x,int v){
        for(x++;x<=n;x+=x&-x)t[x]+=v;
    }
    int ask(int x){
        if(x<0)return 0;
        x=min(x,n-1);
        int res=0;
        for(x++;x;x-=x&-x)res+=t[x];
        return res;
    }
};

struct SegUnion {
    int n;
    set<int> s;
    BIT cnt,sum;

    SegUnion() {}
    SegUnion(int n):n(n),cnt(n+1),sum(n+1){}

    void addgap(int x,int v){
        if(x<=0)return;
        cnt.add(x,v);
        sum.add(x,x*v);
    }

    void add(int x){
        if(s.count(x))return;

        auto it=s.lower_bound(x);

        int l=-1,r=-1;
        if(it!=s.end())r=*it;
        if(it!=s.begin())l=*prev(it);

        if(l!=-1&&r!=-1)addgap(r-l,-1);
        if(l!=-1)addgap(x-l,1);
        if(r!=-1)addgap(r-x,1);

        s.insert(x);
    }

    void del(int x){
        auto it=s.find(x);
        if(it==s.end())return;

        int l=-1,r=-1;

        auto jt=next(it);
        if(jt!=s.end())r=*jt;
        if(it!=s.begin())l=*prev(it);

        if(l!=-1)addgap(x-l,-1);
        if(r!=-1)addgap(r-x,-1);
        if(l!=-1&&r!=-1)addgap(r-l,1);

        s.erase(it);
    }

    int ask(int l){
        if(s.empty()||l<=0)return 0;

        int c=cnt.ask(l);
        int sm=sum.ask(l);
        int tot=sz(s)-1;

        return l+sm+(tot-c)*l;
    }
};
vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    z[0] = n;

    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }

        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }

        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}
vi get(string s,string t){
    string s1=s+"#"+t;
    vi z=z_function(s1);
    vi z1(t.size());
    for(int i=s.size()+1;i<s1.size();i++){
        z1[i-s.size()-1]=z[i];
    }
    return z1;
}
void solve() {
    int a,b,c;
    cin>>a>>b>>c;
    string a1,b1,c1;
    cin>>a1>>b1>>c1;
    vi z1=get(a1,b1);
    vi z2=get(a1,c1);
    int ans=0;
    vvi cnt1(a+1);
    vi cnt2(a+1);
    for(int i=0;i<z1.size();i++)cnt1[z1[i]].pb(i);
    for(int i=0;i<z2.size();i++)cnt2[z2[i]]++;
    for(int i=a-1;i>=0;i--){
        cnt2[i]+=cnt2[i+1];
    }
    SegUnion st(a);
    for(int i=a;i>=1;i--){
        for(auto j:cnt1[i]){
            st.add(j);
        }
        ans+=st.ask(i)*cnt2[i];
    }
    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

1008. 病毒片段

• 线段树segtree
• 离散化coordinate_compression
• 离线查询offline_queries
• 扫描线sweeping

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 5;
void init() {}
struct SegTree {
    int n;
    vector<int> tr;

    SegTree(int n) : n(n) {
        tr.assign(4 * n + 5, 0);
    }

    void pushup(int p) {
        tr[p] = max(tr[p << 1], tr[p << 1 | 1]);
    }

    void update(int p, int l, int r, int x, int v) {
        if (l == r) {
            tr[p] = max(tr[p], v);
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) update(p << 1, l, mid, x, v);
        else update(p << 1 | 1, mid + 1, r, x, v);
        pushup(p);
    }

    int query(int p, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return tr[p];
        }
        int mid = (l + r) >> 1;
        int res = 0;
        if (L <= mid) res = max(res, query(p << 1, l, mid, L, R));
        if (R > mid) res = max(res, query(p << 1 | 1, mid + 1, r, L, R));
        return res;
    }

    void update(int x, int v) {
        update(1, 1, n, x, v);
    }

    int query(int l, int r) {
        return query(1, 1, n, l, r);
    }
};
void solve() {
    int n,q;
    cin >> n>>q;
    vpii a(n);
    vi d;
    for(int i = 0; i < n; i++){
        cin >> a[i].f >> a[i].s;
        d.pb(a[i].f);
        d.pb(a[i].s);
    }
    vpii qs(q);
    for(int i = 0; i < q; i++){
        cin >> qs[i].f >> qs[i].s;
        d.pb(qs[i].f);
        d.pb(qs[i].s);
    }
    sort(all(d));
    d.erase(unique(all(d)), d.end());
    vvi st(sz(d)+1);
    vvpii qs1(sz(d)+1);
    SegTree tr(sz(d)+1);
    for(int i = 0; i < n; i++){
        a[i].f = lower_bound(all(d), a[i].f) - d.begin()+1;
        a[i].s = lower_bound(all(d), a[i].s) - d.begin()+1;
        st[a[i].s].pb(a[i].f);
    }
    for(int i = 0; i < q; i++){
        qs[i].f = lower_bound(all(d), qs[i].f) - d.begin()+1;
        qs[i].s = lower_bound(all(d), qs[i].s) - d.begin()+1;
        qs1[qs[i].s].pb({qs[i].f, i});
    }
    vi ans(q);
    for(int i = 1; i <= sz(d); i++){
        for(auto x: st[i]){
            tr.update(x, d[i-1]-d[x-1]+1);
        }
        for(auto x: qs1[i]){
            ans[x.s] = tr.query(x.f, i);
        }
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << endl;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

1009. 自乘

• 函数图functional_graph
• 中国剩余定理crt
• 扩展欧几里得算法extended_euclidean
• 置换环分解permutation_cycle_decomposition

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'

const int mod = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 5;

void init() {}
using ll = long long;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1;
    ll g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

pair<ll, ll> CRT(vector<ll> a, vector<ll> b) {
    ll r = 0, m = 1;

    for (int i = 0; i < a.size(); i++) {
        ll x, y;
        ll g = exgcd(m, a[i], x, y);

        if ((b[i] - r) % g != 0)
            return {-1, -1};

        ll mod = a[i] / g;

        __int128 t = (__int128)(b[i] - r) / g * x;
        t %= mod;

        r = (r + (__int128)m * t) % (m / g * a[i]);
        if (r < 0)
            r += m / g * a[i];

        m = m / g * a[i];
    }

    return {r, m};
}
pair<int, int> ps2(int L, int target) {
    if (L == 1)
        return {0, 1};

    int now = 1;

    for (int q = 0;; q++) {
        if (now == target) {
            int period = 1;
            int x = 2 % L;

            while (x != 1) {
                x = x * 2 % L;
                period++;
            }

            return {q, period};
        }

        now = now * 2 % L;

        if (now == 1)
            break;
    }

    return {-1, -1};
}
void solve() {
    int n;
    cin >> n;
    vi a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    int k = ceil(log2(n));
    for (int i = 0; i <= k; i++) {
        if (a == b) {
            cout << i << endl;
            return;
        }
        vi c(n + 1);
        for (int j = 1; j <= n; j++) {
            c[j] = a[a[j]];
        }
        a = c;
    }
    vi deg(n + 1);
    for (int i = 1; i <= n; i++) {
        deg[a[i]]++;
    }
    vi vis(n + 1);
    vvi g;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && deg[i]) {
            int cur = i;
            vi cycle;
            while (!vis[cur]) {
                vis[cur] = 1;
                cycle.pb(cur);
                cur = a[cur];
            }
            g.pb(cycle);
        }
    }
    vi tg(n + 1, -1);
    for (int i = 1; i <= n; i++) {
        if (tg[a[i]] == -1) {
            tg[a[i]] = b[i];
        } else {
            if (tg[a[i]] != b[i]) {
                cout << -1 << endl;
                return;
            }
        }
    }
    vi a1, b1;

    for (auto &x : g) {
        vi d;

        for (auto y : x) {
            d.pb(tg[y]);
        }

        vi d1 = x;

        auto it = find(all(d1), d[0]);

        if (it == d1.end()) {
            cout << -1 << endl;
            return;
        }

        int shift = it - d1.begin();

        rotate(d1.begin(), d1.begin() + shift, d1.end());

        if (d != d1) {
            cout << -1 << endl;
            return;
        }

        int L = sz(d);
        int target = (shift + 1) % L;

        auto [q0, period] = ps2(L, target);

        if (q0 == -1) {
            cout << -1 << endl;
            return;
        }

        a1.pb(period);
        b1.pb(q0);
    }

    auto ans = CRT(a1, b1);

    if (ans.f == -1) {
        cout << -1 << endl;
        return;
    }

    cout << ans.f + k + 1 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    cin >> t;

    while (t--) solve();

    return 0;
}

1010. 链上 Nim

• 异或线性基xor_basis
• 博弈论game_theory
• 位掩码bitmask

#include <iostream>
#include <bitset>

using namespace std;

typedef __uint128_t i128;

struct LB {
    i128 b[128]{};
    int v[128]{};

    void insert(i128 x, int s) {
        for (int i = 127; i >= 0; --i) {
            if (x >> i & 1) {
                if (b[i]) {
                    x ^= b[i];
                    s ^= v[i];
                }
                else {
                    b[i] = x;
                    v[i] = s;
                    return;
                }
            }
        }
    }

    int query(i128 x) {
        int res = 0;
        for (int i = 127; i >= 0; --i) {
            if (x >> i & 1) {
                if (b[i]) {
                    x ^= b[i];
                    res ^= v[i];
                }
                else return -1;
            }
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        LB lb;
        int k;
        cin >> k;
        while (k--) {
            int c, s;
            cin >> c >> s;
            i128 msk = 0;
            while (c--) {
                int t;
                cin >> t;
                msk ^= i128(1) << t;
            }
            lb.insert(msk, s);
        }
        int q;
        cin >> q;
        while (q--) {
            int d;
            cin >> d;
            i128 msk = 0;
            while (d--) {
                int t;
                cin >> t;
                msk ^= i128(1) << t;
            }
            cout << lb.query(msk) << '\n';
        }
    }
    return 0;
}

1012. 仙人掌图

• 树形 DPdp_tree
• 树trees
• 组合数学combinatorics
• 深度优先搜索dfs

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 200010;
const int MOD = 998244353;
vector<pair<int, int>> adj[N];
int g[N], f[N]; // val, len
LL res;
LL fac[N], fac2[N];

void init() {
    int n = 200000;
    fac[0] = fac2[0] = fac2[1] = 1;
    for (int i = 1; i <= n; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    for (int i = 2; i <= n; ++i) {
        fac2[i] = fac2[i - 2] * i % MOD;
    }
}

bool dfs(int x, int fa) {
    map<int, map<int, int>> mp;
    for (auto [w, y] : adj[x]) {
        if (y == fa) continue;
        if (!dfs(y, x)) return false;
        if (w == 1 && g[y] != 1 || f[y] && f[y] != w) return false;
        if (w != 1 && w != g[y] + 1) mp[w][g[y]]++;
    }
    // cout << "calculating " << x << '\n';
    for (auto [val, smp] : mp) {
        auto it = smp.begin();
        while (!smp.empty()) {
            if (smp.find(val - it->first - 1) == smp.end()) {
                if (g[x] || it->second != 1) return false;
                else {
                    g[x] = it->first + 1;
                    f[x] = val;
                    it = smp.erase(it);
                }
            }
            else if (it->first * 2 + 1 == val) {
                if (g[x] && (it->second & 1)) return false;
                else if (it->second & 1) {
                    g[x] = it->first + 1;
                    f[x] = val;
                    if (it->second - 2 >= 0) {
                        res = res * fac2[it->second - 2] % MOD * it->second % MOD;
                        // cout << "c1" << fac2[it->second - 2] % MOD * it->second % MOD << '\n';
                    }
                }
                else {
                    res = res * fac2[it->second - 1] % MOD;
                    // cout << "c2" << fac2[it->second - 1] << '\n';
                }
                it = smp.erase(it);
            }
            else {
                auto r = smp.find(val - it->first - 1);
                if (g[x] && it->second != r->second || abs(it->second - r->second) > 1) return false;
                else if (it->second == r->second) {
                    res = res * fac[it->second] % MOD;
                    // cout << "d0" << fac[it->second] << '\n';
                }
                else if (it->second == r->second + 1) {
                    g[x] = it->first + 1;
                    f[x] = val;
                    res = res * fac[it->second] % MOD;
                    // cout << "d1" << fac[it->second] << '\n';
                }
                else {
                    g[x] = r->first + 1;
                    f[x] = val;
                    // cout << "d2" << fac[r->second] << '\n';
                    res = res * fac[r->second] % MOD;
                }

                r = smp.erase(r);
                it = smp.erase(it);
            }
        }
    }
    if (!g[x]) g[x] = 1;
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init();
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        fill(g, g + n + 1, 0);
        fill(f, f + n + 1, 0);
        for (int i = 1; i <= n; ++i) adj[i].clear();
        for (int i = 1; i < n; ++i) {
            int x, y, z;
            cin >> x >> y >> z;
            adj[x].emplace_back(z, y);
            adj[y].emplace_back(z, x);
        }
        res = 1;
        if (!dfs(1, 0) || g[1] != 1) cout << 0 << '\n';
        else cout << res << '\n';
    }
    return 0;
}