题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5593
题意：
http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=654&pid=1004
题解：
先自底向上跑一遍，求出以u为根的子树中与u距离小于等于k的节点数(不同的距离要分开存，否则无法递推上去，dp[u][i]存距离为i的节点数）
求好之后，再dfs一遍，这次换做自顶向下，目的是求u的兄弟（和兄弟的后代）以及u的祖先（和祖先的后代，不包括以u为根的子树）中与u距离小于等于k的节点数（也是分开存）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn=5e5+;
typedef long long LL; int dp[maxn][];
int fa[maxn];
int N,K,A,B; struct Edge{
int v,ne;
Edge(int v,int ne):v(v),ne(ne){}
Edge(){}
}egs[maxn*]; int head[maxn],tot; void addEdge(int u,int v){
egs[tot]=Edge(v,head[u]);
head[u]=tot++;
}
//从下往上跑一遍
void dfs1(int u){
int p=head[u];
while(p!=-){
Edge& e=egs[p];
dfs1(e.v);
for(int i=;i<=K;i++){
//转移方程1：
dp[u][i]+=dp[e.v][i-];
}
p=e.ne;
}
dp[u][]=;
}
//从上往下跑一遍
void dfs2(int u){
if(fa[u]){
for(int i=K;i>=;i--){
//转移方程2：
dp[u][i]+=dp[fa[u]][i-]-dp[u][i-];//dp[fa[u]][i-1]有包括u本身，所以要扣掉u的那部分对fa[u]的贡献
}
dp[u][]++;
}
int p=head[u];
while(p!=-){
Edge& e=egs[p];
dfs2(e.v);
p=e.ne;
}
} void init(){
fa[]=;
memset(dp,,sizeof(dp));
memset(head,-,sizeof(head));
tot=;
} int main(){
int tc;
scanf("%d",&tc);
while(tc--){
scanf("%d%d%d%d",&N,&K,&A,&B);
init();
for(int i=;i<=N;i++){
int x=((LL)A*i+B)%(i-)+;
addEdge(x,i);
fa[i]=x;
}
dfs1();
dfs2();
LL ans=;
for(int i=;i<=N;i++){
int cnt=;
for(int j=;j<=K;j++) cnt+=dp[i][j];
ans^=cnt;
}
printf("%lld\n",ans);
}
return ;
}