【BestCoder Round 65D】【树形DP 容斥思想】ZYB's Tree 求距离每个节点距离不超过k的节点数

本文主要是介绍【BestCoder Round 65D】【树形DP 容斥思想】ZYB's Tree 求距离每个节点距离不超过k的节点数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

ZYB's Tree

Accepts: 77

Submissions: 513

Time Limit: 3000/1500 MS (Java/Others)

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

问题描述

 $Z Y B$ 有一颗 $N$ 个节点的树,现在他希望你对于每一个点,求出离每个点距离不超过 $K$ 的点的个数.两个点 $(x, y)$ 在树上的距离定义为两个点树上最短路径经过的边数,为了节约读入和输出的时间,我们采用如下方式进行读入输出:读入:读入两个数 $A, B$ ,令 $fa_i$ 为节点 $i$ 的父亲, $fa_1=0$ ; $fa_i=(A*i+B)\%(i-1)+1$   $\in [2,N]$  .输出:输出时只需输出 $N$ 个点的答案的 $x o r$ 和即可。

输入描述

第一行一个整数 $T$ 表示数据组数。接下来每组数据：一行四个正整数 $N, K, A, B$ .最终数据中只有两组 $\geq 100000$ 。 $\leq T \leq 5$ , $\leq N \leq 500000$ , $\leq K \leq 10$ , $\leq A,B \leq 1000000$

输出描述

 $T$ 行每行一个整数表示答案.

输入样例

1
3 1 1 1

输出样例

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1,class T2>inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template <class T1,class T2>inline void gmin(T1 &a,T2 b){if(b<a)a=b;}
const int N=5e5+10,M=1e6+10,Z=1e9+7,ms63=1061109567;
int casenum,casei;
int n,K,A,B;
int first[N],id;
int w[M],nxt[M];
bool e[N];
int f[N][12],ans;
inline void ins(int x,int y)
{++id;w[id]=y;nxt[id]=first[x];first[x]=id;
}
void dfs(int x)
{e[x]=1;f[x][0]=1;for(int i=1;i<=K;++i)f[x][i]=0;for(int z=first[x];z;z=nxt[z]){	int y=w[z];if(e[y])continue;dfs(y);for(int i=1;i<=K;++i)f[x][i]+=f[y][i-1];}
}
void dp(int x)
{e[x]=0;for(int z=first[x];z;z=nxt[z]){int y=w[z];if(!e[y])continue;for(int i=K;i>=2;--i)f[y][i]+=f[x][i-1]-f[y][i-2];++f[y][1];dp(y);}int tmp=0;for(int i=0;i<=K;++i)tmp+=f[x][i];ans^=tmp;
}
int main()
{scanf("%d",&casenum);for(casei=1;casei<=casenum;++casei){scanf("%d%d%d%d",&n,&K,&A,&B);memset(first,0,n+2<<2);id=0;for(int i=2;i<=n;++i){int j=((LL)A*i+B)%(i-1)+1;ins(i,j);ins(j,i);}ans=0;dfs(1);dp(1);printf("%d\n",ans);}return 0;
}
/*
【trick&&吐槽】
1，csy向我透露说，这次BC有题可以暴力过！
于是我就写了个暴力，然后TLE……
果然还是要自己思考，不能再被骗了23332，A和B都是1e6范围的数，所以乘法可能会爆int，一定要注意啊>_<3，这么水的题比赛时候竟然没认真想过，我好蠢！【题意】
给你一棵树，树上有n（5e5）个节点，让你求出，对于所有点而言的，距离不超过K（1<=K<=10）的节点数。
然后输出这所有节点数的异或和。【类型】
树形DP【分析】
首先，这是树结构。
然后，我们尝试简化问题。
如果求的，不是对于一个节点，所有距离在[1,K]的节点数，而是限制在子树内的距离在[1,K]的节点数。
那么，这道题，我们直接一个dfs就可以搞定。
就是从叶子节点开始，距离这个节点距离为[1,K]的节点数。
然后f[x][i]=∑f[son][i-1]，i∈[1,K]f[x][0]=1然而，我们还要求与非子树内的节点，怎么办呢？
我们做完之前的预处理之后，只需要从父节点寻求转移即可。我们假设，我们已经知道了距离父节点x距离为0~K的所有点的点数。我们现在要向子节点y转移。
显然，f[y][i]+=f[x][i-1]-f[y][i-2]，2<=i<=K。++f[y][1];
意思是，距离父节点x为i-1的节点，转移到节点y的时候，距离就变成了i。
然而， 并非所有的节点都能做转移。y子树内的，距离为y为i-2的节点，距离父节点的距离也是i-1，但是距离y的距离并非为i。
所以我们把这些节点剔除。一个转移从子节点转移而来，另外一个转移从父节点转移而来。
同时DP的时候要注意使用合理的拓扑序，就可以顺利AC这道题啦。啦啦啦啦~【时间复杂度&&优化】
O（nk）【数据】
调试代码——
for(int i=1;i<n;++i)
{int x,y;scanf("%d%d",&x,&y);ins(x,y);ins(y,x);
}
input
14 5 1 1
1 2
2 3
3 4
4 5
1 6
6 7
7 8
8 9
9 10
1 11
11 12
12 13
13 14
output
8
*/

这篇关于【BestCoder Round 65D】【树形DP 容斥思想】ZYB's Tree 求距离每个节点距离不超过k的节点数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！