记录编号	586494	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]树之美	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.967 s
提交时间	2024-01-27 19:24:37	内存使用	51.80 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 5e5+10;
int t,n,k,A,B,ans;
struct made{
	int ver,nx;
}e[N<<1];
int hd[N],tot,f[N][15];
void add(int x,int y){
	e[++tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
	e[++tot].nx = hd[y],e[tot].ver = x,hd[y] = tot;
}
void first(){
	tot = 0;ans = 0;
	memset(hd,0,sizeof hd);
	memset(f,0,sizeof f);
}
void dfs1(int x,int fa){
	f[x][0] = 1;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y == fa)continue;
		dfs1(y,x);
		for(int j = 1;j <= k;j++)f[x][j] += f[y][j-1];
	}
}
void dfs2(int x,int fa){
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y == fa)continue;
		for(int j = k;j >= 2;j--)f[y][j] += f[x][j-1] - f[y][j-2];
		f[y][1]++;
		dfs2(y,x);
	}
	int s = 0;
	for(int j = 0;j <= k;j++)s += f[x][j];
	ans ^= s;
}
int main(){
	freopen("skytree.in","r",stdin);
	freopen("skytree.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		first(); 
		scanf("%d%d%d%d",&n,&k,&A,&B);
		for(int i = 2;i <= n;i++)add(i,(1ll*A*i+B)%(i-1)+1);
		dfs1(1,0);
		dfs2(1,0);
		printf("%d\n",ans);
	}
	
	return 0;
	
}