HA NOIP2025迷惑行为大赏

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
#define Luogu return
#define AeeE5x 0
using namespace std;

int n;
long long m;
struct node{long long x,y;}a[100010];

long long ans=0;
vector<long long> vec;

int main(){
//	freopen("..\\samples\\candy\\candy6.in","r",stdin);
//	freopen("..\\samples\\candy\\candy.out","w",stdout);
	freopen("candy.in","r",stdin);
	freopen("candy.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	
	long long minxy=infll;
	for(int i=1;i<=n;i++) minxy=min(minxy,a[i].x+a[i].y);
	
	for(int i=1;i<=n;i++) vec.push_back(a[i].x);
	vec.push_back(0);
	sort(vec.begin(),vec.end());
	for(int i=1;i<(int)vec.size();i++) vec[i]+=vec[i-1];
	
	for(int i=0;i<(int)vec.size();i++){
		if(vec[i]>m) break;
		ans=max(ans,(m-vec[i])/minxy*2+i);
	}
	cout<<ans<<"\n";
	
//	#ifdef TakanashiHoshino
//	cerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";
//	#endif
	Luogu AeeE5x;
}

/*

8:31 
感觉 T1 比较简单
能一直买的条件显然就是 x+y 最小

怎么感觉像个橙。。 有种不好的预感。。 

8:33
还需要处理其他情况，先想想特殊性质 
这个特殊性质给的还是很多的 

x_i=y_i？
那就是不管买谁都一样，所以答案就是 \lfloor \frac{m}{\min_x} \rfloor

x_i\ge y_i？
挑一个 x+y 最小的一直买
还剩下的不够这个 x+y 的钱选择可能的 x 买 

8:43
怎么被第四个大洋里 hack 了。。 
说明这场大洋里比较强，是好事吧。。 

9:06

3 10
5 5
1 100
2 100

hack 

x+y 最小的有可能是诈骗，实际上不买这个 x+y 会有更大的价值 

9:15
可以枚举不受若干次诈骗能得到的价值 
过掉所有阳历，试试对拍 

9:19
拍了 100 组，没有问题 
好吧我收回刚才的话，我感觉这有黄 
开 T2 吧。 

*/

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
#define Luogu return
#define AeeE5x 0
using namespace std;

const long long mod=998244353;
long long fac[5010],fac_inv[5010];
long long C(long long n,long long m){return fac[n]*fac_inv[n-m]%mod*fac_inv[m]%mod;}
long long qpow(long long x,long long a){
	long long res=1;
	while(a){
		if(a&1) res=res*x%mod;
		x=x*x%mod;
		a>>=1;
	}
	return res;
}
void fac_init(long long n){
	fac[0]=fac_inv[0]=1;
	for(long long i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	fac_inv[n]=qpow(fac[n],mod-2);
	for(long long i=n-1;i>=1;i--) fac_inv[i]=fac_inv[i+1]*(i+1)%mod;
}

int n,m;
long long a[5010];

void solve_A(){
	cout<<qpow(2,n)<<"\n";
}
void solve_B(){
	long long ans=qpow(2,n);
	for(int cnt1=0;cnt1<=m;cnt1++){
		if(cnt1+(n-cnt1)*2<=m) continue;
		if((m-cnt1)&1) (ans+=(mod-C(n,cnt1))%mod)%=mod;
	}
	cout<<ans<<"\n";
}
void solve_C(){
	long long ans=qpow(2,n);
	
	int p=upper_bound(a+1,a+1+n,a[n]/2)-a;
	(ans+=(mod-(n-p)*qpow(2,p-1)%mod)%mod)%=mod;
	
	for(int i=p;i<n;i++){
		int pp=upper_bound(a+i+1,a+n,a[n]-a[i])-a;
		(ans+=(mod-qpow(2,i-1)*(n-pp)%mod)%mod)%=mod;
	}
	
	cout<<ans<<"\n";
}

long long b[5010];
long long dp[10010];

struct node{
	long long x,w;
	bool operator<(const node&_Q)const{return x*(w==1?2:1)<_Q.x*(_Q.w==1?2:1);}
}d[5010];

long long pppans=0;

void bf(){
	pppans=0;
	for(int bitmask=0;bitmask<(1<<n);bitmask++){
		for(int i=1;i<=n;i++){
			if(bitmask&(1<<(i-1))) b[i]=a[i]/2,d[i]={a[i],2};
			else b[i]=a[i],d[i]={a[i],1};
		}
		for(int i=1;i<=n;i++) for(int j=m;j>=b[i];j++) dp[j]=max(dp[j],dp[j-b[i]]+a[i]);
		sort(d+1,d+1+n);
		long long pans=0;
		long long nowm=m;
		for(int i=1;i<=n;i++) if(nowm>=d[i].w) nowm-=d[i].w,pans+=d[i].x;
		long long rans=0;
		for(int i=0;i<=m;i++) rans=max(rans,dp[i]);
		
		if(pans==rans) pppans++;
		
		
	}
	cout<<pppans<<"\n";
	
	
	
}

int main(){
//	freopen("..\\samples\\sale\\sale7.in","r",stdin);
//	freopen("..\\samples\\sale\\sale.out","w",stdout);
	freopen("sale.in","r",stdin);
	freopen("sale.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	int testid,T;cin>>testid>>T;
	fac_init(5000);
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];
		sort(a+1,a+1+n);
		
		if(testid==18||testid==16) solve_A();
		else if(testid==10||testid==11||testid==12||testid==19||testid==20) solve_B();
		else bf();
	} 
	
	#ifdef TakanashiHoshino
	cerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";
	#endif
	Luogu AeeE5x;
}

/*

9:23
咋还有多测啊。。
n\le 5000 是和一位 

首先小 X 可以给所有糖都定成 1，这样小 R 可以获得前 m 大的价值
可能会存在 rank m 相等的情况？。。

呃呃不对我读错题了。。
这个意思是经典 01 背包的贪心策略在多少种方案情况下是真的。。

小 X 可以选择把一些数除以 2，然后小 R 以性价比贪心策略选数，问有多少种除以 2 的方案使小 R 的贪心是真的。

9:29
这个有点难算，试试能不能用用 hxf 熔池？
先考虑性价比，再考虑原价，考虑编号没区别

9:38
没什么头绪，看看特殊性质试试

a_1=a_2=\dots =a_n
所有原价都相等，选择除以二的性价比一定低，一定会最后选，所以会先选完 w=1 的
那就是不管怎么定价，策略总是正确的 
答案就是 2^n。

m=2n-1
只有全都除以二才拿不到所有数。
但是全都除以二之后大小关系也一定一样，所以所有方案均合法，答案是 2^n。

9:52（？） 
我草等会电脑这个表不准现在已经 9:56 了 
感觉今年 sale 严格大于 assign 啊。。
我草怎么都十点了！！

11:14
假完了。变成 8pts 了。 
再见 NOIP。 

12:41
可能也没什么人能看到这吧。顺手推点歌？ 

Nanatsukaze - 真空都市
Nanatsukaze - Aria
A4。 - 天使の翼。

*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl putchar('\n')
#define pc(ch) putchar(ch)
const int N = 8e3 + 5;
int n, m, T, a[N], ans, sum, fa[N];
vector <int> vt[N];
int read(){
	char ch = getchar(), type = ch;
	int res = 0;
	while (!isdigit(ch))type = ch, ch = getchar();
	while (isdigit(ch)){
		res = (res << 3) + (res << 1) + (ch ^ 48);
		ch = getchar();
	}
	return (type == '-' ? ((res ^ -1) + 1) : res);
}
void write(int x){
	if (x < 0){
		putchar('-');
		x = (x ^ -1) + 1;
	}
	int sta[105], top = 0;
	do {
		sta[++top] = x % 10;
		x /= 10;
	} while (x != 0);
	for (; top >= 1; --top){
		putchar(sta[top] + 48);
	}
}
void dfs(int u){
	int len = vt[u].size();
	if (!len){
		if (a[u] == 0)++sum;
		return;
	}
	for (int i = 0; i < len; ++i){
		int v = vt[u][i];
		dfs(v);
	}
	for (int i = 0; i <= n + 1; ++i){
		int flag = 0;
		for (int j = 0; j < len; ++j){
			if (a[vt[u][j]] == i){
				flag = 1;
				break;
			}
		}
		if (a[u] == i){
			flag = 1;
		}
		if (!flag){
			sum += i;
			break;
		}
	}
	return;
}
void ddfs(int u){
	if (u > n){
		sum = 0;
		dfs(1);
		ans = max(ans, sum);
		return;
	}
	for (int i = 0; i <= n; ++i){
		a[u] = i;
		ddfs(u + 1);
	}
}
signed main(){
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
//	cin.tie(0)->sync_with_stdio(0);
	T = read();
	while (T--){
		n = read(), m = read(), ans = 0;
		for (int i = 2; i <= n; ++i){
			fa[i] = read();
			vt[fa[i]].push_back(i);
		}
		ddfs(1);
		write(ans);
		endl;
	}
	return 0;
}
/*
000
//freopen
feropen
freopne
afo/ll 
我常常追忆过去。
中间忘了。 
我该在哪里停留？我问我自己。 
recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall!
recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall!
recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall!
recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall!
recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall!
recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall recall!







 rrrrrrrr       eeeeeeeeee      cccccccccc       aaaaaaaa       l               l
r        r      e               c               a        a      l               l
r        r      e               c               a        a      l               l
r        r      e               c               a        a      l               l
rrrrrrrrrr      e               c               a        a      l               l
r  r            eeeeeeeeee      c               aaaaaaaaaa      l               l
r   r           e               c               a        a      l               l
r    r          e               c               a        a      l               l
r     r         e               c               a        a      l               l
r      r        e               c               a        a      l               l
r       r       eeeeeeeeee      cccccccccc      a        a      llllllllll      llllllllll

12:17。 
/ll/ll/ll 

YatohgamiTohka
TobiichiOrigami
Kurumi
DATE A LIVE


Genshin Impact
299133621


Luogu:718169 



By __int127
。 
Yy:喵 


Why?

*/

#include <bits/stdc++.h>
#define frr(a) freopen(a, "r", stdin)
#define fww(a) freopen(a, "w", stdout)
#define MP make_pair
#define eb emplace_back
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
struct FaatIO {
	char gc() {
		return getchar();
	}
	template <typename T> void read(T& x) {
		char c = gc(), l = 0; x = 0;
		while (!isdigit(c)) l = c, c = gc();
		while ( isdigit(c)) x = x * 10 + c - '0', c = gc();
		if (l == '-') x = -x;
	}
	bool bk(char c) {
		return c == ' ' || c == '\r' || c == '\n' || c == '\t';
	}
	void read(string &x) {
		x.clear(); char c = gc();
		while ( bk(c)) c = gc();
		while (!bk(c)) x += c, c = gc();
	}
	template <typename T, typename ...A> void read(T& x, A&... a) {
		read(x), read(a...);
	}
} IO;
const int N = 1e5 + 10;
struct node {
	ll x, y;
	int id;
} a[N];
ll n, m;
bool cmp1(node a, node b) {
	int sa = a.x + a.y, sb = b.x + b.y;
	if (sa == sb) {
		return a.x < a.y;
	} return sa < sb;
}
bool cmp2(node a, node b) {
	return a.x < b.x;
}
int main() {
	frr("candy.in");
	fww("candy.out");
	IO.read(n, m); ll stm = m;
	for (int i = 1; i <= n; i++) {
		IO.read(a[i].x, a[i].y);
		a[i].id = i;
	}
	sort(a + 1, a + n + 1, cmp1);
	ll s = a[1].x + a[1].y; int pid = a[1].id;
//	printf("m:%lld s:%lld\n", m, s);
	
	ll res, nw; 
	res = nw = (m / s) * 2; 
	m %= s;
	
	ll lst[2] = {a[1].x, a[1].y};
//	printf("m:%lld nw:%lld lst0:%lld lst1:%lld\n", m, nw, lst[0], lst[1]);
	
	sort(a + 1, a + n + 1, cmp2);
	
	//以买偶数个结尾
	ll tot = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i].id == pid) continue;
		int x = a[i].x;
		while (m < x) {
			if (!nw) break;
			nw -= 2; m += s;
		}
		if (m >= x) {
			tot++;
//			printf("nw:%lld tot:%lld\n", nw, tot);
			m -= x; res = max(res, nw + tot);
		} 
		if (nw <= 0) break;
	}
	
	m = stm, nw = (m / s) * 2;
	m %= s;
	if (m >= lst[0]) nw++, m -= lst[0];
	else nw--, m += lst[1];
	res = max(res, nw);
	
	tot = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i].id == pid) continue;
		int x = a[i].x;
		while (m < x) {
			if (!nw) break;
			nw -= 2; m += s;
		}
		if (m >= x) {
			tot++;
//			printf("nw:%lld tot:%lld\n", nw, tot);
			m -= x; res = max(res, nw + tot);
		} 
		if (nw <= 0) break;
	}
	
	
	printf("%lld\n", res);
	return 0;
}
/*
写的真是一大坨啊。
神入_ANIG_上厕所忘带准考证。
*/

/*
1h20min : 大样例6 7 过不去
会少
1h25min : 找到了错误的地方，但是不会改 
1h40min 感觉要完蛋了啊 
先打一下后面的暴力换换心情吧，错误：
后两种情况，有可能会选到其他的两个x, y
如：
2 
3 
4 
114514 1
m ： 114515
最优方案：2 + 3 + 4，怎么选到呢？ 
指针？指向当前x最小的两个，如果1 + 114514 < 2 + 3， 则选1 + 114514, 
否则选一个x，向后移1位，再判断1 + 114514 < 3 + 4 ? 


2h : 好不容易想到的方法发现是假的
那就写暴力吧 
*/ 
#include<bits/stdc++.h>
#define endl '\n';
using namespace std;

const int N = 1e5 + 10;
long long m, res, tx, ty, ans;
int n;
int tp[N];
bool xza = true, xzb = true; 

struct zyc{
	int x, y;
}a[N];

bool cmp(zyc xx, zyc yy)
{
	return xx.x + xx.y < yy.x + yy.y;
}

void dfs(int stp, long long ans, long long v)
{
	if(stp > n)
	{
		res = max(res, ans);
		return;
	}
	long long cnt = 0;
	dfs(stp + 1, ans, v);
	for(int i = 1; i <= 20; i ++)
	{
		if(i % 2) cnt += a[stp].x;
		else cnt += a[stp].y;
		if(cnt > m - v) break;
		dfs(stp + 1, ans + i, v + cnt);
	}
}

int main()
{
	freopen("candy.in", "r", stdin);
	freopen("candy.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i].x >> a[i].y;
		if(a[i].x != a[i].y) xza = false;
		if(a[i].x < a[i].y) xzb = false;
	}
	if(n <= 10 && m <= 20)
	{
		sort(a + 1, a + n + 1, cmp);
		bool flag = true;
		for(int i = 1; i <= n; i ++) if(a[i].x != 1 || a[i].y != -1) flag = false;
		if(flag)
		{
			cout << m << endl;
		}else{
			dfs(1, 0ll, 0ll);
			cout << res << endl;
		} 
	}else if(xza)
	{
		//特殊性质A， 15pts 
		sort(a + 1, a + n + 1, cmp);
		cout << m * 1ll / (a[1].x) << endl; 
	}else if(xzb){
		sort(a + 1, a + n + 1, cmp);
		tx = a[1].x, ty = a[1].y;
		long long z = m / (1ll * tx + ty);
		m %= (1ll * tx + ty);
		res += 2ll * z;
		for(int i = 1; i <= n; i ++) tp[i] = a[i].x;
		sort(tp + 1, tp + n + 1);
		for(int i = 1; i <= n; i ++)
		{
			if(tp[i] <= m)
			{
				res ++;
				m -= tp[i];
			}else break;
		}
		cout << res << endl;
	}else{
		sort(a + 1, a + n + 1, cmp);
		tx = a[1].x, ty = a[1].y;
		
		long long z = m / (1ll * (tx + ty));
		long long nwm = m % (1ll * (tx + ty));
		
		//case 1: 选完 max * (tx + ty)
		long long tnwm = nwm;
		ans = 2ll * z;
		for(int i = 1; i <= n; i ++) tp[i] = a[i].x;
		sort(tp + 1, tp + n + 1);
		for(int i = 1; i <= n; i ++)
		{
			if(tp[i] <= tnwm)
			{
				ans ++;
				tnwm -= tp[i];
			}else break;
		}
		if(ans > res) res = ans;
		//cout << res << endl;
		
		//case 2: (max - 1) * (tx + ty) + tx
		tnwm = nwm + ty;
		ans = 2ll * (z - 1) + 1;
		//cout << tnwm << " " << ans << endl;
		tp[1] = a[1].y;
		for(int i = 2; i <= n; i++) tp[i] = a[i].x;
		sort(tp + 1, tp + n + 1);
		if(ans > res) res = ans;
		//cout << res << endl;
		//case 3: (max - 1) * (tx + ty)
		tnwm = nwm + tx + ty;
		ans = 2ll * (z - 1);
		for(int i = 1; i <= n; i ++) tp[i] = a[i].x;
		sort(tp + 1, tp + n + 1);
		for(int i = 1; i <= n; i ++)
		{
			if(tp[i] <= tnwm)
			{
				ans ++;
				tnwm -= tp[i];
			}else break;
		}
		if(ans > res) res = ans;
		
		cout << res << endl;
	}
	
	
	return 0;
}
//freopen
//luogu : yueluoxingchen
//第一年进NOIP就遇到了神秘小孩，看身高感觉像xxs 

/*
~一道橙题~ 
完了完了NOIP要爆零了怎么办？
唱几首歌证明来过？
//freopen("candy.in","r",stdin); 钓鱼

戏一折 水袖起落
唱悲欢 唱离合 无关我
扇开合 锣鼓响又默
戏中情 戏外人 凭谁说 

惯将喜怒哀乐都藏入粉墨
陈词唱穿又如何
白骨青灰皆我 
乱世浮萍忍看烽火燃山河
位卑未敢忘忧国
哪怕无人知我

台下人走过 不见旧颜色
台上人唱着 情碎离别歌
情字难落寞 她唱需以血来和
戏幕起 戏幕落 谁是客

你方唱罢我登场
莫嘲讽月戏 莫笑人荒唐
也曾问青黄 也曾铿锵唱兴亡
道无情 道有情 怎思量

道无情 道有情 最思量 
*/

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

const int N=1e5+5;

struct Node{
	int v1,v2,sum,x;
}a[N];

int n,m,res;

bool p=0,vis[N],k[N];

bool cmp(Node a,Node b){
	return a.sum<b.sum;
}

bool cmp2(Node a,Node b){
	return a.v1<b.v1;
}

bool cmp3(Node a,Node b){
	int p,q;
	if(vis[a.x])p=a.v2;
	else p=a.v1;
	if(vis[b.x])q=b.v2;
	else q=b.v1;
	return p<q;
}

signed main(){
	freopen("candy.in","r",stdin);
	freopen("candy.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].v1>>a[i].v2;
		a[i].sum=a[i].v1+a[i].v2;
		a[i].x=i;
	}
	sort(a+1,a+n+1,cmp);
	sort(a+2,a+n+1,cmp2);
	for(int i=1;i<=n;i++){
		if(a[i].v1>a[1].v1&&!p&&m>a[1].v1){
			p=1;
			i--;
			res++;
			m-=a[1].v1;
			k[a[1].x]++;
			continue;
		}else if(2*a[i].v1<=a[1].v1+a[1].v2&&m>a[i].v1){
			m-=a[i].v1;
			vis[a[i].x]=1;
			k[a[i].x]++;
			res++;
		}
	}
	if(p)m+=a[1].v1,res--;
	//剩的钱贪心购买1
	res+=(m/a[1].sum)*2;
	k[a[1].x]+=(m/a[1].sum)*2;
	m-=(m/a[1].sum*a[1].sum);

	sort(a+1,a+n+1,cmp3);
	//最后贪心买1,2 
	for(int i=1;i<=n;i++){
		int t;
		if(vis[a[i].x])t=a[i].v2;
		else t=a[i].v1;
		if(m>=t){
			m-=t;
			k[a[i].x]++;
			res++;
		}else{
			break;
		}
	}
	cout<<res;
	return 0;
} 
//猜难度:绿蓝紫黑 
//猜对了就求上迷惑行为大赏   

/*
一年四季的更替
竹篱下的乱花影
温柔的风刚过季
像还在自己家里

故乡的那一封信
是谁在不问归期
酒馆的老伙计也有
思念瘦的回忆

烛灯下的旧情 意谁理
西窗外的良人 泣不易
举杯 谁和明月提起
她在远方等你
等你 在落下几笔
等你 再弹奏几曲
等你 再回到故里
等你 金榜把名题

砚上三五笔
落寞遮鸪啼
谁识曲中意
断弦等你系

哎呦小情郎你莫愁
此生只为你挽红袖
三旬酒过月上枝头
我心悠悠

哎呦小娘子你莫忧
待到春来又雪满楼
不负天长不负地久
你我白首 
*/ 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=5e3+5,mod=998244353;

int c,t,n,m,a[N],f[N],vis[515],maxx=-1,dp[12][22],cnt;

map<int,int>mp;

struct Node{
	int x,w,y;
}k[N];

bool cmp(Node a,Node b){
	return a.x>b.x;
}

bool cmp2(int a,int b){
	return a>b;
}

void dfs(int deep){
	if(deep>n){
		for(int i=1;i<=n;i++){
			k[i].x=a[i]*2/f[i];
			k[i].y=a[i];
			k[i].w=f[i]; 
//			cout<<f[i]<<" ";
		}
//		cout<<endl;
		sort(k+1,k+n+1,cmp);
		int t=m,res=0;
		for(int i=1;i<=n;i++){
//			cout<<k[i].y<<" ";
			if(t>=k[i].w){
				t-=k[i].w;
				res+=k[i].y;
			}
		}
//		cout<<endl;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(j>=f[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-f[i]]+a[i]);
				else dp[i][j]=dp[i-1][j];
			}
		}
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=m;j++){
////				cout<<dp[i][j]<<" ";
//			}
//			cout<<endl;
//		}
//		cout<<res<<endl<<endl;
		if(dp[n][m]==res)cnt++;
		return;
	}
	f[deep]=1;
	dfs(deep+1);
	f[deep]=2;
	dfs(deep+1);
}

signed main(){
	freopen("sale.in","r",stdin);
	freopen("sale.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>c>>t;
	if(c<=5){
		//n*m*2^n*t,n<=10理论卡常可过 
		while(t--){
			cin>>n>>m;
//			cout<<m<<endl;
			for(int i=1;i<=n;i++){
				cin>>a[i]; 
			}
			dfs(1);
			cout<<cnt<<endl;
		}
	}
	if((c>=18&&c<=20)||(c>=10&&c<=12)){
		while(t--){
			cin>>n>>m;
			for(int i=1;i<=n;i++){
				cin>>a[i];
			}
			int res=1;
			while(n--){
				res*=2;
				res%=mod;
			}//斯，不会快速幂咋整？ 
			cout<<res<<"\n";
		}
	}
	if(c==16){
		while(t--){
			cin>>n>>m;
			for(int i=1;i<=n;i++){
				cin>>a[i];
			}
			int rs=1;
			while(n--){
				rs*=2;
				rs%=mod;
			}
			for(int i=1;i<=n;i++){
				k[i].x=a[i]*2/f[i];
				k[i].y=a[i];
				k[i].w=i; 
			}
			sort(k+1,k+n+1,cmp);
			int t=m,res=0;
			for(int i=1;i<=n;i++){
				if(m>f[i]){
					m-=f[i];
					res+=k[i].y;
				}
			}
			sort(a+1,a+n+1,cmp2);
			int res2=0;
			for(int i=1;i<n;i++){
				res2+=a[i];
			}
			if(res!=res2)rs=(rs-1+mod)%mod;
			cout<<rs<<"\n";
		}
	}
	if((c>=7&&c<=9)||(c>=14&&c<=15)){
		while(t--){
			cin>>n>>m;
			for(int i=1;i<=n;i++){
				cin>>a[i];
				maxx=max(maxx,a[i]);
			}
			int S1=0,S2=-1,S3=0;
			for(int i=1;i<=n;i++){
				if(a[i]*2<maxx){
					S1++;
				}else{
					S2++;
				}
				if(a[i]*2==maxx)S3++;
			}
			int res1=1,res2=1,res3=1;
			while(S1--){
				res1*=2;
				res1%=mod;
			}
			while(S2--){
				res2*=2;
				res2%=mod;
			}
			while(S3--){
				res3*=2;
				res3%=mod;
			}
			int res=(res1*res2)%mod-(res3*res1)%mod;
			cout<<res<<endl;
		}
	}
	
	return 0;
} 

/*
时常梦我 染上相思轮廓
你生炉暖火 斟暖我心窝
雨打蕉叶 胜过美人坡
在泼墨画里 鱼儿也快活 

时常梦到 是否梦到过我
爱恨我了然 而缘很稀薄
二胡声唤你 隐去江南
我为你挥毫旧谣一番

姑娘一句春不晚 痴儿留在真江南 
江南曲落孤城 化作烟雨 与我对谈
姑娘一句冬不寒 痴儿踏过万重山
记得我们的歌 轻声叹

为啥总感觉我哪里唱错了 -_-|| 
*/
#include <bits/stdc++.h>
using namespace std;

const int N=8005;

int T,n,m,a[N],p[N],vis[N],dis[N];

queue<int>q;

int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	cin>>T;
	while(T--){
		int res=0,k=0;
		memset(p,0,sizeof(p));
		memset(vis,0,sizeof(vis));
		memset(dis,0,sizeof(dis));
		cin>>n>>m;
		for(int i=2;i<=n;i++){
			cin>>a[i];
			p[a[i]]++;
		}
		for(int i=1;i<=n;i++){
			if(!p[i]){
				if(!vis[a[i]]){
					q.push(a[i]);
					if(!vis[i])k++;
					vis[a[i]]=1;
					dis[a[i]]=p[a[i]]+1;
				}
			}
		}
		while(!q.empty()){
			int t=q.front();q.pop();
			if(a[t]==0)continue;
			dis[a[t]]=max(dis[a[t]],dis[t]+1);
			if(vis[a[t]])continue;
			vis[a[t]]=1;
			q.push(a[t]);
		}
		for(int i=1;i<=n;i++)res+=dis[i];
		cout<<res+k<<endl;
	}
	return 0;
}