hdu5593 / bestcoder round #65 1004 ZYB's Tree 树形dp

http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=654&pid=1004

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=500010;
const int INF=1<<29;

ll dp[maxn][12],dp2[maxn][12];
int N,K,A,B;
int fa[maxn];
vector<int> G[maxn];

ll dfs(int u,int x)
{
    if(x<0) return 0;
    ll &res=dp[u][x];
    if(~res) return res;
    res=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        res+=dfs(v,x-1);
    }
    return res;
}

ll dfs2(int u,int x)
{
    if(x<0) return 0;
    ll &res=dp2[u][x];
    if(~res) return res;
    res=dfs(u,x);
    if(u==1||x==0) return res;
    res+=dfs2(fa[u],x-1);
    res-=dfs(u,x-2);
    return res;
}

int main()
{
    //freopen("in.txt","r",stdin);
    int T;cin>>T;
    while(T--){
        scanf("%d%d%d%d",&N,&K,&A,&B);
        REP(i,1,N) G[i].clear();
        fa[1]=0;
        REP(i,2,N) fa[i]=(A*1LL*i+B)%(i-1)+1;
        REP(i,2,N) G[fa[i]].push_back(i);
        memset(dp,-1,sizeof(dp));
        memset(dp2,-1,sizeof(dp2));
        ll ans=0;
        //REP(i,1,N) cout<<dfs(i,K)<<" ";cout<<endl;
        //REP(i,1,N) cout<<dfs2(i,K)<<" ";cout<<endl;
        REP(i,1,N) ans^=dfs2(i,K);
        printf("%I64d
",ans);
    }
    return 0;
}

/** 
题意：
    给一颗树，求对于树中的每个点u，设距离u不超过K的点的个数为f(u)(包括u)，
    求每个f(u)。
分析：
    由于K很小，所以可以dp。
    设u的子树(包括u)中距离u不超过x的点的个数为dp(u,x)，
    整个树(1~n)中距离u不超过x的的点的个数为dp2(u,x)，
    dp(u,x)=dp(u,x)+dp2(f,x-1)-dp(u,x-2)
    dp(u,0)=1;
    dp(u,x)=0 (x<0);
类型：
    树形dp
注意事项：
    按方程直接dfs+记忆化就可以了，不用写得太复杂。。。
坑点：
    没有。
总结：
    第一道自己想出来的树形dp。不过把异或^符号写成|了，wrong了几次。。。。
    树形dp似乎也不是很难。。
*/