2025牛客暑期多校训练营10-做题&补题记录

十场全部结束，暑假也不剩几天了，该写OS课设了（悲

最后rk184，金线rk173，差一点，罚时太多，磕头谢罪了

不过这个金银也没啥用倒也没区别就是了（

总的来说打的没去年多校那么坐牢了，不好说这是不是最后一年多校，但总之尽力了就好

---

D Grammar Test (grammar)

由著名公式swap(x,y)->x^=y^=x^=y，发现将三个x和y相互异或分组，奇数组就可保证可相互交换。而只要有两个相邻元素相等，某个数必定变为0，则必无解，所以答案要么是0要么是2。

但是我不知道在干什么，上来WA3发，磕头了！

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T1,typename T2>
ostream& operator<<(ostream& o,const tuple<T1,T2>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T1,typename T2,typename T3>
ostream& operator<<(ostream& o,const tuple<T1,T2,T3>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";
}

template<typename T,const size_t S>
ostream& operator<<(ostream& o,const array<T,S>& arr){
	for(int i=(o<<"[",0);i<S;++i)o<<arr[i]<<(i+1<S?",":"");
	return o<<"]\n";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	for(int i=(o<<"[",0);i<vec.size();++i)o<<vec[i]<<(i+1<vec.size()?",":"");
	return o<<"]\n";
}

constexpr int M = 2e5+5, mod = 998244353;// 1e9+7;
constexpr double pi = acos(-1), eps = 1e-9;

void solve(){
	ll n;
	cin>>n;
	n--;
	cout<<(n%6==3?2:0)<<"\n";
	
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t{1};
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

H Rev Equation (NOI-tAUqe ver.) (equation)

唐题。变成的回文串必须最短，所以两个数相等必无解。减法需要特判，0-x=的形式可以变成0=x-x=0，其余情况无解。剩余情况两个操作数不等的加法和乘法，由于是阿贝尔群，必有解。

/*

This code template was updated by Yukii_P on 2025/8/9.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }
template<typename T, size_t S>
ostream& operator<<(ostream& o, array<T, S>& x) { for (int i = (o << "[", 0); i < S; ++i) o << x[i] << (i + 1 < x.size() ? ", " : ""); return o << "]";}
template<typename T>
ostream& operator<<(ostream& o, vector<T>& x) { for (int i = (o << "[", 0); i < x.size(); ++i) o << x[i] << (i + 1 < x.size() ? ", " : ""); return o << "]";}

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = ", dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2> 
void dbg2(T x, T2... args) { std::cerr << ", " << x; dbg2(args...); }
template<typename T, typename... T2> 
void dbg1(T x, T2... args) { std::cerr << x; dbg2(args...); }
template<typename T> 
void dbg1(std::vector<T> x, int s) { s = std::min<int>(s, x.size()); for (int i = (std::cerr << "[", 0); i < s; ++i) std::cerr << x[i] << (i + 1 < s ? ", " : "]\n"); }
#else
#define debug(...) 
#endif

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    string s;
    cin >> s;
    if (s[0] == s[2]|| (s[1]=='-'&&s[0]!='0')) {
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

F Sensei and Yuuka Going Shopping (yuuka)

思洋写的，填坑待补。

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T1,typename T2>
ostream& operator<<(ostream& o,const tuple<T1,T2>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T1,typename T2,typename T3>
ostream& operator<<(ostream& o,const tuple<T1,T2,T3>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";
}

template<typename T,const size_t S>
ostream& operator<<(ostream& o,const array<T,S>& arr){
	for(int i=(o<<"[",0);i<S;++i)o<<arr[i]<<(i+1<S?",":"");
	return o<<"]\n";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	for(int i=(o<<"[",0);i<vec.size();++i)o<<vec[i]<<(i+1<vec.size()?",":"");
	return o<<"]\n";
}

constexpr int M = 150005, mod = 998244353, inf = 1e9;
constexpr double pi = acos(-1), eps = 1e-9;

ll v[M<<2],t[M<<2],tag1[M<<2],tag2[M<<2];

void build(int now,int l,int r){
	tag1[now]=-inf;
	tag2[now]=0;
	v[now]=0;
	if(l==r)return;
	int mid=l+r>>1;
	build(now<<1,l,mid),build(now<<1|1,mid+1,r);
	return;
}

void update1(int now,ll x){
	v[now]=x;
	tag1[now]=x;
	tag2[now]=0;
	return;
}

void update2(int now,ll x){
	if(tag1[now]>-inf)return update1(now,tag1[now]+x);
	v[now]+=x;
	tag2[now]+=x;
	return;
}

void push_down(int now){
	if(tag1[now]>-inf)update1(now<<1,tag1[now]),update1(now<<1|1,tag1[now]);
	if(tag2[now])update2(now<<1,tag2[now]),update2(now<<1|1,tag2[now]);
	return tag1[now]=-inf,tag2[now]=0,void();
}

void change(int now,int l,int r,int L,int R,ll x){
	if(l>R||L>r)return;
	if(L<=l&&r<=R)return update1(now,x);
	push_down(now);
	int mid=l+r>>1;
	change(now<<1,l,mid,L,R,x),change(now<<1|1,mid+1,r,L,R,x);
	v[now]=max(v[now<<1],v[now<<1|1]);
	return;
}

void add(int now,int l,int r,int L,int R,ll x){
	if(l>R||L>r)return;
	if(L<=l&&r<=R)return update2(now,x);
	push_down(now);
	int mid=l+r>>1;
	add(now<<1,l,mid,L,R,x),add(now<<1|1,mid+1,r,L,R,x);
	v[now]=max(v[now<<1],v[now<<1|1]);
	return;
}

ll query(int now,int l,int r,int L,int R){
	if(l>R||L>r)return -inf;
	if(L<=l&&r<=R)return v[now];
	push_down(now);
	int mid=l+r>>1;
	return max(query(now<<1,l,mid,L,R),query(now<<1|1,mid+1,r,L,R));
}

void solve(){
	int n;
	cin>>n;
	build(1,1,n);
	unordered_map<int,vector<int>> p;
	vector<int> a(n);
	for(auto& i:a)cin>>i;
	for(int i=n;i>=1;--i){
		int x=a[i-1];
		p[x].emplace_back(i);
	}
	int ans=0,ansl=0,ansr=0;
	unordered_set<int> vis;
	for(int i=1;i<=n;++i){
		auto& cur=p[a[i-1]];
		cur.pop_back();
		if(!vis.contains(a[i-1])){
			vis.insert(a[i-1]);
			if(cur.size()>=2){
				int l=cur.back(),r=cur.front();
				add(1,1,n,l+1,r,1);
			}
		}
		else{
			if(cur.size()<=0){
				continue;
			}
			int l=i,r=cur.back();
			add(1,1,n,l+1,r,-1);
		}
		int s=query(1,1,n,1,n);
		if(s>ans){
			ans=s;
			ansl=i+1;
		}
	}
	unordered_map<int,int> cnt[3];
	for(int i=0;i<ansl-1;++i)cnt[0][a[i]]=1;
	for(int i=ansl-1;i<n;++i)cnt[1][a[i]]++;
	for(int t=0,i=ansl-1;i<n-1;++i){
		cnt[2][a[i]]++,cnt[1][a[i]]--;
		if(!cnt[0].contains(a[i]))continue;
		if(cnt[1][a[i]]==0)--t;
		if(cnt[2][a[i]]==1)++t;
		if(t==ans){
			ansr=i+2;
			break;
		}
	}
	if(!ans)ansl=2,ansr=3;
	cout<<ans<<"\n"<<ansl<<" "<<ansr<<"\n";
	
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t{1};
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

I Matrix (matrix)

当且仅当n和m互质时有解。构造方法是，从第一行开始，左右横跳填满一行，再上下跳到新行，继续左右横跳，重复这个过程直到填满。正确性不会证，求一个数论高手。

/*

This code template was updated by Yukii_P on 2025/8/9.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }
template<typename T, size_t S>
ostream& operator<<(ostream& o, array<T, S>& x) { for (int i = (o << "[", 0); i < S; ++i) o << x[i] << (i + 1 < x.size() ? ", " : ""); return o << "]";}
template<typename T>
ostream& operator<<(ostream& o, vector<T>& x) { for (int i = (o << "[", 0); i < x.size(); ++i) o << x[i] << (i + 1 < x.size() ? ", " : ""); return o << "]";}

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = ", dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2> 
void dbg2(T x, T2... args) { std::cerr << ", " << x; dbg2(args...); }
template<typename T, typename... T2> 
void dbg1(T x, T2... args) { std::cerr << x; dbg2(args...); }
template<typename T> 
void dbg1(std::vector<T> x, int s) { s = std::min<int>(s, x.size()); for (int i = (std::cerr << "[", 0); i < s; ++i) std::cerr << x[i] << (i + 1 < s ? ", " : "]\n"); }
#else
#define debug(...) 
#endif

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    int x = 0, y = 0, c = 0;
    int flag = 0;
    int f2 = 0;
    int ok = 1;
    vector<int> cnt(n);
    for (int id = 1; id <= n * m; ++id) {
        if (a[x][y]) {
            ok = 0;
            break;
        }
        a[x][y] = id;
        cnt[x]++;
        if (cnt[x] != m) {
            if (flag) {
                y += id;
                y %= m;
            } else {
                y -= id;
                y %= m;
                y += m;
                y %= m;
            }
            flag ^= 1;
        } else {
            if (f2) {
                x += id;
                x %= n;
            } else {
                x -= id;
                x %= n;
                x += n;
                x %= n;
            }
            f2 ^= 1;
        }
    }
    if (!ok) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << a[i][j] << " \n"[j == m - 1];
        }
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

E Sensei and Affection (affection)

爱丽丝还没补喵，爱丽丝一定补喵喵喵

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T1,typename T2>
ostream& operator<<(ostream& o,const tuple<T1,T2>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T1,typename T2,typename T3>
ostream& operator<<(ostream& o,const tuple<T1,T2,T3>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";
}

template<typename T,const size_t S>
ostream& operator<<(ostream& o,const array<T,S>& arr){
	for(int i=(o<<"[",0);i<S;++i)o<<arr[i]<<(i+1<S?",":"");
	return o<<"]\n";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	for(int i=(o<<"[",0);i<vec.size();++i)o<<vec[i]<<(i+1<vec.size()?",":"");
	return o<<"]\n";
}

constexpr int M = 2e5+5, mod = 998244353;// 1e9+7;
constexpr double pi = acos(-1), eps = 1e-9;

void solve(){
	int n,m;
	cin>>n>>m;
	vector<int> a(n);
	for(auto& i:a)cin>>i;
	int ans=1e9;
	if(m==1){
		for(int i=n-1;i;--i){
			a[i]-=a[i-1];
		}
		int cur=0,x=0,t=0;
		for(int j=1;j<n;++j){
			if(a[j]>cur){
				int d=a[j]-cur;
				if(d<=x){
					x-=d;
				}
				else{
					d-=x;
					x=0;
					t+=d;
				}
			}
			else{
				int d=cur-a[j];
				x+=d;
				t+=d;
			}
		}
		ans=min(ans,t);
	}
	else{
		int mx=ranges::max(a),mn=ranges::min(a);
		for(int l=mn;l<=mx;++l){
			for(int r=mx;r<=mx+n;++r){
				int dpl=l-a[0],dpr=r-a[0];
				for(int i=1;i<n;++i){
					int ndpl=1e9,ndpr=1e9;
					if(a[i]<=l){
						if(a[i-1]<=l){
							ndpl=min(ndpl,max(0,a[i-1]-a[i])+dpl);
						}
						ndpl=min(ndpl,max(0,l-a[i]-r+a[i-1])+dpr);
					}
					if(a[i-1]<=l){
						ndpr=min(ndpr,max(0,r-a[i]-l+a[i-1])+dpl);
					}
					ndpr=min(ndpr,max(0,a[i-1]-a[i])+dpr);
					dpl=ndpl,dpr=ndpr;
				}
				ans=min({ans,dpl,dpr});
			}
		}
	}
	cout<<ans<<"\n";
	
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t{1};
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

K Amazing Sets (amazing)

先跑SCC缩点，然后按照逆拓扑序合并集合，这个过程中维护bitset记录答案。合并过程比较有讲究，类似启发式合并，把小的集合并到大的里面，这里遍历1个数少的bitset，放入多的，复杂度就控制住了。

/*

This code template was updated by Yukii_P on 2025/8/9.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }
template<typename T, size_t S>
ostream& operator<<(ostream& o, array<T, S>& x) { for (int i = (o << "[", 0); i < S; ++i) o << x[i] << (i + 1 < x.size() ? ", " : ""); return o << "]";}
template<typename T>
ostream& operator<<(ostream& o, vector<T>& x) { for (int i = (o << "[", 0); i < x.size(); ++i) o << x[i] << (i + 1 < x.size() ? ", " : ""); return o << "]";}

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = ", dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2> 
void dbg2(T x, T2... args) { std::cerr << ", " << x; dbg2(args...); }
template<typename T, typename... T2> 
void dbg1(T x, T2... args) { std::cerr << x; dbg2(args...); }
template<typename T> 
void dbg1(std::vector<T> x, int s) { s = std::min<int>(s, x.size()); for (int i = (std::cerr << "[", 0); i < s; ++i) std::cerr << x[i] << (i + 1 < s ? ", " : "]\n"); }
#else
#define debug(...) 
#endif

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 1e4 + 10;
constexpr int MOD = 998244353;

vector<int> e[N];
int a[N];
int dfn[N], low[N], tot;
int stk[N], instk[N], top;
int scc[N], siz[N], cnt, cntt;
i64 s[N];
set<int> ans[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    stk[++top] = u, instk[u] = 1;
    for (int v : e[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        int v; cnt++;
        do {
            v = stk[top--];
            instk[v] = 0;
            scc[v] = cnt;
            siz[cnt]++;
            s[cnt] += a[v];
        } while (v != u);
        if (siz[cnt] > 1) cntt++;
    }
}

void solve() {
    int n;
    // cin >> n;
    read(n);
    // vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        // cin >> a[i];
        read(a[i]);
    }
    // vector<vector<int>> e(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        // cin >> u >> v;
        read(u, v);
        e[u].push_back(v);
    }
    int m;
    // cin >> m;
    read(m);
    //set<tuple<int, int>> sst;
    for (int i = 0; i < m; ++i) {
        int u, v;
        // cin >> u >> v;
        read(u, v);
        //if (u == v) continue;
        //if (sst.count({u, v})) continue;
        e[u].push_back(v);
        //sst.insert({u, v});
    }
    for (int i = 1; i <= n; ++i) {
        if (dfn[i]) continue;
        tarjan(i);
    }
    // debug(cnt);
    vector<int> ind(cnt + 1,0);
    vector<vector<int>> e2(cnt + 1);
    for (int u = 1; u <= n; ++u) {
        for (int v : e[u]) {
            if (scc[u] == scc[v]) continue;
            e2[scc[u]].push_back(scc[v]);
            ind[scc[v]]++;
        }
    }
    // for (int i = 1; i <= cnt; ++i) cout << ind[i] << " \n"[i == cnt];
    for (int i = 1; i <= cnt; ++i) {
        if (ind[i] == 0) {
            e2[0].push_back(i);
        }
    }
    vector<int> b(cnt + 1, -1);

    // int ans = 0;
    vector<bitset<10010> > st(cnt + 1);
    // for (int i = 1; i <= cnt; ++i) cout << s[i] << " \n"[i == cnt];
    auto dfs = [&](auto&& dfs, int u) -> int {
        if (b[u] != -1) return b[u];
        int res = s[u];
        st[u].set(0);
        for (int v : e2[u]) {
            // debug(u, v);
            res += dfs(dfs, v);
            bitset<10010> tmp;
            int a = u, b = v;
            if(st[a].count() > st[b].count()) swap(a, b);
            
            for (int i = st[a]._Find_first(); i != st[a].size(); i = st[a]._Find_next(i)) {
                tmp |= (st[b] << i);
            }
            st[u]=tmp;
        }
        st[u].set(res);
        // st[u]=tmp;
        return b[u] = res;
    };
    dfs(dfs, 0);
    // st.set(0);
    cout << st[0].count() << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/