ZYB's Tree

Memory Limit: 131072/131072 K (Java/Others)

问题描述

ZYBZYB有一颗NN个节点的树,现在他希望你对于每一个点,求出离每个点距离不超过KK的点的个数.

两个点(x,y)(x,y)在树上的距离定义为两个点树上最短路径经过的边数,

为了节约读入和输出的时间,我们采用如下方式进行读入输出:

读入:读入两个数A,BA,B,令fa_ifai为节点ii的父亲,fa_1=0fa1=0;fa_i=(A*i+B)\%(i-1)+1fai=(A∗i+B)%(i−1)+1 i \in [2,N]i∈[2,N] .

输出:输出时只需输出NN个点的答案的xorxor和即可。

输入描述

第一行一个整数TT表示数据组数。

接下来每组数据：

 一行四个正整数N,K,A,BN,K,A,B.

 最终数据中只有两组N \geq 100000N≥100000。

1 \leq T \leq 51≤T≤5,1 \leq N \leq 5000001≤N≤500000,1 \leq K \leq 101≤K≤10,1 \leq A,B \leq 10000001≤A,B≤1000000

输出描述

TT行每行一个整数表示答案.

输入样例

1

3 1 1 1

输出样例

题解：定义dp[i][j]为以i为根距离为j的点的个数

定义dp2[i][j] 在除去i的子树的点中，与点i距离为j的点的个数

在遍历图求出dp[][]后

对于fa,son

我们求dp2的转移方程就是

dp2[son][h]=dp[fa][h-1]-dp[son][h-2]+dp[fa][h-1];

//meek

#include <iostream>

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

#include <queue>

#include <map>

#include <set>

#include <stack>

#include <sstream>

#include <vector>

using namespace std ;

typedef long long ll;

#define mem(a) memset(a,0,sizeof(a))

#define pb push_back

#define fi first

#define se second

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//****************************************

const int N=+;

const ll inf = 1ll<<;

const int mod= ;

int a,b,K,n;

int vis[N];

vector<int >G[N];

int nex;

int dp[N][],dp2[N][];

void dfs(int x) {

    dp[x][]=;

    for(int i=;i<G[x].size();i++) {

        dfs(G[x][i]);

        for(int j=;j<=K;j++) {

            dp[x][j]+=dp[G[x][i]][j-];

        }

    }

}

int main() {

    int T;

    scanf("%d",&T);

    while(T--) {

            mem(dp),mem(dp2);

        scanf("%d%d%d%d",&n,&K,&a,&b);

        for(int i=;i<=N;i++) G[i].clear();

        for(int i=;i<=n;i++) {

           ll fa=(a+b)%(i-)+;

            G[fa].pb(i);

        }int A=,ans;

        dfs();

        for(int i=;i<=n;i++) {

                for(int j=;j<G[i].size();j++) {

                    dp2[G[i][j]][]=dp[i][];

                    for(int h=;h<=K;h++)

                        dp2[G[i][j]][h]=dp[i][h-]-dp[G[i][j]][h-]+dp2[i][h-];

                }

                ans=;

            for(int j=;j<=K;j++) {

                ans+=dp[i][j]+dp2[i][j];

            }

             A^=ans;

        }

       printf("%d\n",A);

    }

    return ;

}

代码

秒客网

hdu5593/ZYB's Tree 树形dp

ZYB's Tree

相关文章