COGS 2532. [HZOI 2016]树之美树形dp

112 阅读 0 评论 74 点赞

我是靠谱客的博主细腻水杯，最近开发中收集的这篇文章主要介绍COGS 2532. [HZOI 2016]树之美树形dp，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

可以发现这道题的数据范围有些奇怪，为毛n辣么大，而k只有10

我们从树形dp的角度来考虑这个问题。

如果我们设f[x][k]表示与x距离为k的点的数量，那么我们可以O(1)回答一个询问

可是这样的话dp貌似就比较麻烦了。

我们考虑一般树形dp都是怎样的，一般的树形dp，都是因为子树上的f值可以无后效的转移到根节点上，并且子树的f值与父亲无关，如果我们按照上述定义，那么就会发现这需要两遍dfs来解决，并且细节不少。

但是两遍dfs我并不会QAQ

所以我们考虑转换一种定义，设f[x][k]表示在以x为根的子树中距离不超过k的点数这样就可以很简单地直接dp了，但是统计答案的时候，我们发现一个点的上方的点我们都没有统计。

怎么解决这个问题呢？直接暴力跳转fa，利用fa的f值来补充答案，因为最多向上跳转10次，所以这个做法可行。

复杂度O(nk)

 1 #include <queue>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 typedef long long ll;
 8 inline void read(int &x){
 9
x=0;char ch;bool flag = false;
10
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
11
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
12 }
13 inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
14 inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
15 const int maxn = 500010;
16 const int maxk = 21;
17 int f[maxn][maxk],fa[maxn],n,k;
18 inline void init(){
19
memset(f,0,sizeof f);
20
memset(fa,0,sizeof fa);
21 }
22 inline void work(){
23 
init();
24
int A,B;read(n);read(k);read(A);read(B);
25
int ai;fa[1] = 0;
26
for(int i=2;i<=n;++i){
27
ai = ((ll)A*i + (ll)B )%(i - 1) + 1;
28
fa[i] = ai;
29
//printf("%d %dn",i,fa[i]);
30 
}
31
for(int i=1;i<=n;++i) f[i][0] = 1;
32
for(int j=0;j<k;++j){
33
for(int i=1;i<=n;++i){
34
f[fa[i]][j+1] += f[i][j];
35 
}
36 
}
37
for(int j=1;j<=k;++j){
38
for(int i=1;i<=n;++i){
39
f[i][j] += f[i][j-1];
40 
}
41 
}
42
int ans = 0,res = 0;
43
for(int i=1;i<=n;++i){
44
res = f[i][k];
45
int j = 1,x = fa[i];
46
for(int y=i;x != 0 && j < k;y=x,x=fa[x],++j)
47
res += f[x][k-j] - f[y][k-j-1];
48
if(j == k && x != 0) ++ res;
49
//printf("%d--%dn",i,res);
50
ans ^= res;
51 
}
52
printf("%dn",ans);
53 }
54 int main(){
55
freopen("skytree.in","r",stdin);
56
freopen("skytree.out","w",stdout);
57
int T;read(T);
58
while(T--) work();
59 
getchar();getchar();
60
return 0;
61 }