一个比较简单的 dp。
从暴力到正解实际上只有一个第一眼感觉没用的小优化。
题目链接。
题意
给了你一棵有根树，现在让你在 中选一些点，满足以下要求：
- 需要被选；
- 所有被选的点构成了一棵以
为根的完美二叉树（所有叶子深度一样）。
对于每一个 ，输出答案。
题解
对于每一个节点 ，我们用 表示以 为根的，深度为 的完美二叉树个数。
我们对于每一个 ，重新跑一边dp。
这样子时间复杂度是
的，状态 ，转移均摊 ，还要转移 ，显然过不了。
显然，可以优化一下转移，大概就是对于每一个节点，求一下儿子的 之和。
然后，我们直接枚举一个儿子进行转移就彳亍，不用枚举两个。
这样这个dp就成 的了。
你还会发现，每一次多出来一个点，对他祖先们的dp值，只有一个
发生了变化，我们直接只转移变化的这一位。
时间复杂度是 。
然后你会发现，一棵深度为
的二叉树，节点数高达 。
这题一共就
个节点，二叉树深度最多也就 。
所以对于深度大于
的点，直接不处理了。
同时，对于
的部分，我们也不用处理了。
时间复杂度 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int mod=998244353;
using ll=long long;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
template<const int N,const int M>
struct graph
{
int head[N+5];
int t[M+5];
int x[M+5];
int cntm;
graph(){ cntm=1;}
void clear(int n=N)
{
cntm=1;
for(int i=1;i<=n;i++) head[i]=0;
}
void ad(int u,int v)
{
cntm++;
t[cntm]=v;
x[cntm]=head[u];
head[u]=cntm;
}
void add(int u,int v)
{
ad(u,v);
ad(v,u);
}
int st(int num){ return head[num];}
int to(int num){ return t[num];}
int nx(int num){ return x[num];}
};
graph<300000,600000>g;
ll son[300001][21];
ll dp[300001][21];
int dep[300001];
int fa[300001];
int n;
void dfs(int num)
{
for(int i=g.st(num);i;i=g.nx(i))
{
int p=g.to(i);
if(p==fa[num]) continue;
dep[p]=dep[num]+1,fa[p]=num,dfs(p);
}
}
int main()
{
n=read();
for(int i=2;i<=n;i++) g.add(read(),i);
dfs(1);
for(int i=1;i<=n;i++)
{
if(dep[i]<=20)
{
dp[i][0]=1;ll delta=1;
for(int j=1,nod=fa[i],lst=i;nod;j++,nod=fa[nod],lst=fa[lst])
{
(son[nod][j-1]+=delta)%=mod;
delta=(son[nod][j-1]-dp[lst][j-1]+mod)*delta%mod;
dp[nod][j]=(dp[nod][j]+delta)%mod;
}
}
ll ans=0;
for(int i=0;i<=20;i++) ans=(ans+dp[1][i])%mod;
printf("%lld\n",ans);
}
return 0;
}
|