HUD 5593——ZYB's Tree——————【树形dp】 ZYB's Tree

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 400 Accepted Submission(s): 114

Problem Description

Input

In the first line there is the number of testcases

Output

For

are only for two tests finally.

Sample Input

3 1 1 1

Sample Output

Source

BestCoder Round #65

题目大意：给你一棵无根树，定义了结点距离为任意结点对(i,j)在最短路径上的边的条数。让你求出每个结点的结点距离
小于等于K的结点个数，然后求异或值。
解题思路：我们的总体思路是，先任意定一个根，形成一棵有根树，对于任意的结点，我们可以从距离该结点为K的儿孙结点
和祖先结点两个方面去统计结点个数。我们定义dp[u][j]表示以某个结点u为根的子树中，距离小于等于j的结点个数。现在我们
已经解决了距离该结点为K的儿孙方面的个数，还有祖先方面的需要统计，那么我们可以从结点u向他的祖先结点走，会经过u的父亲
祖父，曾祖父...依次向上。向上走i层，该祖先结点表示为ff，第i-1 层的祖先结点表示为pff。

那么会增加dp[ff][K-i] - dp[pff][K-i-1]个结点。
另外：题中给的1结点的父亲结点0是不用参与运算的。当到达0结点时，可以跳出循环。

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
const int maxn = 550000;
typedef long long LL;
int N,K,A,B;
int f[maxn], dp[maxn][20];
vector<int>G[maxn];
void dfs(int u,int fa){
    for(int i = 0; i <= K; i++){    //初始化以u为子树的根，距离u为i时的结点个数为1
        dp[u][i] = 1;
    }
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v == fa) continue;
        dfs(v,u);
        for(int j = 0; j <= K; j++){    //统计u的所有子节点
            dp[u][j+1] += dp[v][j];
        }
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d",&N,&K,&A,&B);
        for(int i = 0; i <= N+20; i++){
            G[i].clear();
        }
        f[1] = 0;
        for(int i = 2; i <= N; i++){
            int ff = (int)(((LL)A*i+B)%((LL)i-1) + 1);  //计算时会超int
            f[i] = ff;
            G[ff].push_back(i);
        }
        memset(dp,0,sizeof(dp));
        dfs(1,0);
        int ans = 0, tmp;
        for(int u = 1; u <= N; u++){
             tmp = dp[u][K];        //子孙方面个数
             int ff = u;            //初始化祖先结点
             for(int i = 1; i <= K; i++){
                if(i == K){
                    tmp += dp[f[ff]][K-i]; continue;
                }
                if(f[ff] == 0){ //已经到了0结点
                    break;
                }
                tmp += dp[f[ff]][K-i] - dp[ff][K-i-1]; //统计向上经过的满足条件的祖先会贡献多少个结点
                ff = f[ff]; //向祖先走
             }
             ans ^= tmp;    //求每个结点的异或和
        }
        printf("%d
",ans);
    }
    return 0;
}
/*

55
15 3 3 8

*/

HUD 5593——ZYB's Tree——————【树形dp】 ZYB's Tree

相关推荐