Znzryb's Blog

START201——Permutation Cost Sum（排列成环，交换排序）

Posted on 2025-09-12 Edited on 2026-02-18

思路讲解

我们发现，即便我们选了一个这个O(1)的，解决简单问题（单组问题的方法），好像也没什么用？所以说问题难道是引导我们怎么直接计算这个东西？我只能说是无从下手呀。

Cycle decomposition of permutations

这个东西是什么意思那？

https://nor-blog.pages.dev/posts/2023-01-09-permutations-for-beginners/

其实就是排列成环。

我们发现这个无视距离的交换就非常适合用图论来分析。

最后时间复杂度是 $O(N\sqrt N)$ 。

FOR(i, 1, N) {
    if (fa[i] == i) {
        ll freq = cnt[i];
        if (freq == 1)
            continue;
        if (memo[freq]) {
            ans += memo[freq];
            ans %= mod;
            continue;
        }
        ll lans = 0;
        // 这里A的定义和题目里面反过来了，不过我认为都一样
        FOR(a, 1, N) {
            ll b = a - a / freq;
            if (b > 1) {
                // 前面是会变化的 b 来接手
                lans += (freq) * (1 + b - 1) * (b - 1) / 2;
                lans %= mod;
                // 注意 b 的上限是 N
                // 而不是 a
                lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                lans %= mod;
            } else {
                lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                lans %= mod;
            }
        }
        memo[freq] = lans;
        ans += lans;
        ans %= mod;
    }
}

AC代码

https://www.codechef.com/viewsolution/1190700079

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)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 cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())

using namespace std;
#ifdef LOCAL
template <typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template <typename T> void _print(vector<T> v) {
    cerr << "[ ";
    for (T i : v)
        _print(i), cerr << " ";
    cerr << "]";
}
template <typename T> void _print(set<T> s) {
    cerr << "{ ";
    for (T i : s)
        _print(i), cerr << " ";
    cerr << "}";
}
template <typename T, typename U> void _print(pair<T, U> p) {
    cerr << "{";
    _print(p.first);
    cerr << ", ";
    _print(p.second);
    cerr << "}";
}
template <typename T, typename U> void _print(map<T, U> m) {
    cerr << "{ ";
    for (auto &p : m)
        _print(p), cerr << " ";
    cerr << "}";
}
// 打印两层数组，格式好一些
template <typename T> void _print(vector<vector<T>> v) {
    cerr << "{\n";
    for (auto i : v)
        _print(i), cerr << "\n";
    cerr << " }";
}
#endif

using ll = long long;
using ull = unsigned long long;
using ld = double;
using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<ld>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)2e5 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> lT;
    while (lT--)
        __();
    return 0;
}
/*

*/
ll fa[MAXN];
ll cnt[MAXN];
ll find(ll x) {
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}
void merge(ll x, ll y) {
    ll fax = find(x), fay = find(y);
    if (fax == fay)
        return;
    fa[fax] = fay;
    cnt[fay] += cnt[fax];
}
inline void __() {
    cin >> N;
    vll P(N + 5);
    // vector<vll> g(N + 5);
    FOR(i, 1, N) {
        fa[i] = i;
        cnt[i] = 1;
    }
    FOR(i, 1, N) {
        cin >> P[i];
        // g[i].PB(P[i]);
        merge(i, P[i]);
    }
    ll ans = 0;
    vll memo(N + 5);
    FOR(i, 1, N) {
        if (fa[i] == i) {
#ifdef LOCAL
            debug(i);
#endif
            ll freq = cnt[i];
#ifdef LOCAL
            debug(freq);
#endif
            if (freq == 1)
                continue;
            if (memo[freq]) {
                ans += memo[freq];
                ans %= mod;
                continue;
            }
            ll lans = 0;
            // 这里A的定义和题目里面反过来了，不过我认为都一样
            FOR(a, 1, N) {
                ll b = a - a / freq;
                if (b > 1) {
                    // 前面是会变化的 b 来接手
                    lans += (freq) * (1 + b - 1) * (b - 1) / 2;
                    lans %= mod;
                    lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                    lans %= mod;
                } else {
                    lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                    lans %= mod;
                }
// #ifdef LOCAL
//                 debug(lans);
// #endif
            }
            memo[freq] = lans;
            ans += lans;
            ans %= mod;
        }
    }
    cout << ans << "\n";
}
/*

*/

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

START203——Set To Median（sort的魔力）

Posted on 2025-09-11 Edited on 2026-02-18

思路讲解

注释非常详细，看注释就行。

AC代码

https://www.codechef.com/viewsolution/1190317643

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) 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 cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

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 vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--)
		__();
	return 0;
}
/*
只进行一次这个操作以后，要求数组和最大

呃，实话实说，我看了一眼题解，看到了二分答案。
你说这个会是检验这个数组和能不能达到吗？

其实我们会发现，这个也没有那么容易

或者说，我们确定一个数字为中位数以后，检查他是否可行
以及快速O(1)算出答案，可不可行那？
*/
inline void __(){
	cin>>N;
	vll A(N+5);
	FOR(i,1,N){
		cin>>A[i];
	}
	// 发现A的顺序不重要，因此我们进行排序
	sort(A.begin()+1,A.begin()+1+N);
	vll Sum(N+5);
	FOR(i,1,N){
		Sum[i]=Sum[i-1]+A[i];
	}
	// 我们会发现一个瓶颈就是这个O(1)之所以不行，就是因为
	// 就是小的数字我们当然是囊括越多小的越好
	// 但是大的数字我们又希望囊括越少大的数字越好
	// 这个时候就产生了矛盾，我们要怎样最优化这个问题那？
	// 我们注意到 
	// profit=len*A[i]-(A[1]+A[2]+A[3]+...+A[len])+(len*A[i]-(A[i+1]+A[i+2]+...+A[i+len]) )
	// 2*A[i]-A[i+1]-A[1],2*A[i]-A[i+2]-A[2]
	// 不难发现这个是单调下降的，因此用二分就行了
	ll ans=Sum[N];
#ifdef LOCAL
	_print(Sum);
#endif
	FOR(i,2,N){
		ll big=N-i;
		ll l=1,r=big;
		while(l<r){
			ll mid=l+r+1>>1;
			ll p=2*A[i]-A[mid+i]-A[mid];
			if(p>=0){
				l=mid;
			}else{
				r=mid-1;
			}
		}
		if(l==r){
			ll lans=l*A[i]*2-Sum[l]-(Sum[i+l]-Sum[i+1-1])+Sum[N];
			ans=max(lans,ans);
		}
	}
	cout<<ans<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1190317643
1
2
3 4

1
3
4 3 1

*/

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

START203——Subsequences of Subsequences（如何求偶数长度子序列的异或和的最大值）

Posted on 2025-09-11 Edited on 2026-02-18

思路讲解

遇到这种题目不要慌，首先不难发现是线性基。

接着我们不要一下子想特别复杂的情况，我们就想一想 K=2 的时候是怎么样的？

// 因为两段不同的段，相互遮盖的长度是一样的。
// 奇数加奇数是偶数，偶数加偶数还是偶数
// 遮盖以后都是加减偶数，并不会影响段的长度的奇偶性。

    这里用到了一个小技巧

就是这个我们知道，如果说我们只要求偶数长度子序列的
        异或最大值怎么办呢？
        这个时候可以给加入线性基的数字加一个标记，如果最后这个值有标记
        就说明是奇数长度子序列得到的和
        否则就是偶数长度子序列得到的和。

AC代码

https://www.codechef.com/viewsolution/1190285113

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) 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 cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

using  ll = long long; using ull = unsigned long long;
using ld = double; using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>; using plb = pair<ll, bool>;
using pll = pair<ll, ll>; using vll = vector<ll>; using vb = vector<bool>;
using tll = tuple<ll, ll, ll>; using vii = vector<int>;
using vpll = vector<pll>; using vtll = vector<tll>;
using vdb = vector<ld>; using vc = vector<char>;
using arr3 = array<ll, 3> ; using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9+7; // 998244353;
static constexpr double eps = 1e-8; const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> lT;
	while (lT--)
		__();
	return 0;
}
/*
直接模拟肯定不行吗？

用 python 不难得出该结论
*/
vll base;
void add(ll x) {
	FOR(i, 0, SZ(base) -1) {
		x = min(x, x ^ base[i]);
	}
	if (x != 0) base.PB(x);
}
ll count() {
	ll res = 1ll << SZ(base);
	return res;
}
inline void __() {
	cin >> N >> K;
	vll A(N + 5);
	base.clear();
	// 这边需要特判一下。
	if (N == K) {
		ll res = 0;
		FOR(i, 1, N) {
			cin >> A[i];
			res ^= A[i];
		}
		if (res == 0) {
			cout << 1 << "\n";
		} else {
			cout << 2 << "\n";
		}
		return;
	}
	// 因为两段不同的段，相互遮盖的长度是一样的。
	// 奇数加奇数是偶数，偶数加偶数还是偶数
	// 遮盖以后都是加减偶数，并不会影响段的长度的奇偶性。
	if (K & 1) {
		FOR(i, 1, N) {
			cin >> A[i];
			add(A[i]);
		}
		cout <<	count() << "\n";
	} else {
		/*
		这里用到了一个小技巧
		就是这个我们知道，如果说我们只要求偶数长度子序列的
		异或最大值怎么办呢？
		这个时候可以给加入线性基的数字加一个标记，如果最后这个值有标记
		就说明是奇数长度子序列得到的和
		否则就是偶数长度子序列得到的和。
		*/
		ll flag = 1ll << 31;
		FOR(i, 1, N) {
			cin >> A[i];
			add(A[i]^flag);
		}
		ll res = 1ll << (SZ(base) -1);
		// reduced row echelon form （RREF）
		// 我们利用阶梯型行列式REF的性质
		// 只会出现一个含有flag 的数字，因此剪掉就行了。
		cout << res << "\n";
	}
}
/*
AC
https://www.codechef.com/viewsolution/1190285113
1
4 1
1 2 4 8


1
3 3
0 0 0

1
1 1
0

*/

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

START203——MEX on Ranges

Posted on 2025-09-10 Edited on 2026-02-18

思路讲解

其他都想到了，就是这个

reverse(all(wp));

需要hack数据才能想到。

其实1 1 之间不会相互影响，但是0 0之间会，把最重要的放在最远，避免互相影响。

	FOR(i,1,N){
//		if(s[i]=='1') A[i]=i-1;
//		else A[i]=N;
		ll t=N;
		if(s[i]=='1'){
			t=i-1;
			A.PB(t);
			reverse(all(wp));
			for(auto w:wp){
				A.PB(w);
			}
			wp.clear();
		}else{
			t=i-1;
			wp.PB(t);
		}
	}

AC代码

https://www.codechef.com/viewsolution/1189976308

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) 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 cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

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 vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--)
		__();
	return 0;
}
/*

*/
inline void __(){
	cin>>N;
	string s;
	cin>>s;
//	vll A(N+5);
	deque<ll> A;
	vll wp;
	FOR(i,1,N){
//		if(s[i]=='1') A[i]=i-1;
//		else A[i]=N;
		ll t=N;
		if(s[i]=='1'){
			t=i-1;
			A.PB(t);
			reverse(all(wp));
			for(auto w:wp){
				A.PB(w);
			}
			wp.clear();
		}else{
			t=i-1;
			wp.PB(t);
		}
	}
	FOR(i,0,SZ(wp)-1){
		A.PB(N);
	}
	for(auto a:A){
		cout<<a<<" ";
	}
	cout<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1189976308

1
4
11001

既然考虑到了 1 1 的情况，也要考虑0 0 的情况

//		if(i&1){
//			A.PB(t);
//		}else{
//			A.PF(t);
//		}


//	vb suf(N+5);
//	ROF(i,N,0){
//		if(s[i]=='1'){
//			suf[i]=true;
//			continue;
//		}
//		suf[i]=suf[i+1];
//	}
//	FOR(i,1,N){
//		if(s[i]=='1') continue;
//		if(suf[i]){
//			A.PB(i-1);
//		}else{
//			A.PB(N);
//		}
//	}


*/

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

Codeforces Round 1048 (Div. 2)——E2. Maple and Tree Beauty (Hard Version)（bitset的使用，变长bitset）

Posted on 2025-09-10 Edited on 2026-02-18

思路讲解

Codeforces Round 1048 (Div. 2)——E1. Maple and Tree Beauty (Easy Version)（背包问题）（子集枚举→能否凑出某个的和）

不难发现，用背包会TLE。

说实话，这个就真没招了，看题解吧。

其实用bitset 优化一下就能过去。

最后发现，我这样分一个if else 的反而更快

还有一种曲线救国方法。使用模板参数。

template <int maxn>
inline void __() {
//	cin >> N >> K;
	if (maxn <= N) {
		__< min(maxn * 2, (int)MAXN) >();
		return;
	}

AC代码

https://codeforces.com/contest/2139/submission/337943651

$O(N^2/w)$ 的时间复杂度，能够过去。

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <bitset>
#include <vector>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) 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 cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

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 vll = vector<ll>; using vb = vector<bool>;
using tll = tuple<ll, ll, ll>; using vii = vector<int>;
using vpll = vector<pll>; using vtll = vector<tll>;
using vdb = vector<DB>; using vc = vector<char>;
using arr3 = array<ll, 3> ; using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)2e5+10, INF = (ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9+7; // 998244353;
static constexpr double eps = 1e-8; const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> lT;
	while (lT--)
		__();
	return 0;
}
/*
双背包问题解法
https://chatgpt.com/share/68c0ff99-20d0-8013-b16a-26d60768748a


*/
inline void __() {
	cin >> N >> K;
	vll P(N + 5);
	vector<vll> g(N + 5);
	FOR(i, 2, N) {
		cin >> P[i];
		g[i].PB(P[i]);
		g[P[i]].PB(i);
	}
	vll cnt(N + 5);
	ll desti = INF;
	auto dfs = [&](auto &&self, int u, int fa, int dep)->void {
		cnt[dep]++;
		bool isleaf = true;
		for (auto &v : g[u]) {
			if (v == fa) continue;
			self(self, v, u, dep + 1);
			isleaf = false;
		}
		if (isleaf) {
			desti = min<ll>(desti, dep);
		}
	};
	dfs(dfs, 1, 1, 1);
	vll ls = {0};
	FOR(i, 1, desti) {
		ls.PB(cnt[i]);
	}
	// 我们会发现，能否通过前K关（构造出K前缀），和这个顺序是没有关系的
	// 我们直接看前 K 个物品是否可以凑出一个和
	// vector<vii> dp(SZ(ls)+5,vii(N+5));
	if (K <= N - K) {
		K = N - K;
	}
	ll ans = 0;
	if (N <= 200) {
		bitset<210> dp;
		ll sum = 0;
		// 滚动数组优化，第i层哪些值是可以达到的
		dp[0] = true;
		bitset<210> mask;
		FOR(i, 0, K) {
			mask[i] = true;
		}
		ll up = K - N;
		FOR(i, 1, desti) {
			ll w = ls[i];
			sum += w;
			dp |= (dp << w);
			ll cur = sum - N + K - 1;
			FOR(j, max(0ll, up), min(K, cur)) {
#ifdef LOCAL
				debug(j);
#endif
				mask[j] = 0;
			}
			up = cur;
			// 这一大段代码
			// sum-N+K<=val<=K
			if ((mask & dp).any()) {
				ans = i;
			} else {
				break;
			}
		}
	} else {
		bitset<MAXN> dp;
		ll sum = 0;
		// 滚动数组优化，第i层哪些值是可以达到的
		dp[0] = true;
		bitset<MAXN> mask;
		FOR(i, 0, K) {
			mask[i] = true;
		}
		ll up = K - N;
		FOR(i, 1, desti) {
			ll w = ls[i];
			sum += w;
			dp |= (dp << w);
			ll cur = sum - N + K - 1;
			FOR(j, max(0ll, up), min(K, cur)) {
#ifdef LOCAL
				debug(j);
#endif
				mask[j] = 0;
			}
			up = cur;
			// 这一大段代码
			// sum-N+K<=val<=K
			if ((mask & dp).any()) {
				ans = i;
			} else {
				break;
			}
		}
	}
	cout << ans << "\n";
}
/*
AC
https://codeforces.com/contest/2139/submission/337943651
1
5 2
1 1 1 1

*/