[ABC264Ex] Perfect Binary Tree Solution

更好的阅读体验戳此进入

题面

存在一棵以 $1$$1$ 为根节点的 $n$$n$ 个节点的树，给定序列 $P_{n-1}$$P_{n - 1}$ 表示 $[2,n]$$[2, n]$ 节点的父亲。给定 $k$$k$，你需要从 $[1,k]$$[1, k]$ 中选择一些点，对于每一个 $k$$k$ 一次询问，求有多少种选法使得选出的点为一棵以 $1$$1$ 为根节点的满二叉树。输出 $k\in [1,n]$$k \in [1, n]$ 的答案，答案对 $998244353$$998244353$ 取模。

Solution

首先一个比较重要的性质就是 $n$$n$ 个节点的满二叉树层高为 ${\log }_2^n$$\log_2^n$，所以在原树里层高超过 ${\log }_2^n$$\log_2^n$ 的节点就可以直接忽略了。

不难想到 DP，令 $dp(p,i)$$dp(p, i)$ 表示以 $p$$p$ 为根节点层高为 $i$$i$ 的满二叉树方案数。

朴素的转移十分显然，即在其儿子里找到两个层高为 $i-1$$i - 1$ 的满二叉树拼起来即可，即转移为：

考虑到我们每次询问都是增加一个节点，如此的转移方式复杂度显然是不正确的，考虑优化。不难想到这个式子可以转化为从和平方里去除平方和，即：

于是这个东西就可以支持 $O(1)$$O(1)$ 修改了，维护一下和以及平方和即可。注意需要记录上一次的值和新的值，减去旧的加上新的。同时考虑发现每次增加一个点，将会改变该点到 $1$$1$ 节点的整条链，并且只会改变这些点，同时若变化的节点超过 ${\log }_2^n$$\log_2^n$ 层了那么可以直接忽略。

最终的答案即为 $\sum _{i=1}^{\lfloor {\log }_2^n\rfloor }dp(1,i)$$\sum_{i = 1}^{\lfloor \log_2^n \rfloor}dp(1, i)$。

所以每次修改都是 $O(\log n)$$O(\log n)$ 的，最终答案的查询也是 $O(\log n)$$O(\log n)$ 的，最终复杂度 $O(n\log n)$$O(n \log n)$。

Code

xxxxxxxxxx
110
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
struct Edge{
28
    Edge* nxt;
29
    int to;
30
    OPNEW;
31
}ed[610000];
32
ROPNEW(ed);
33
Edge* head[310000];
34

35
ll qpow(ll a, ll b){
36
    ll ret(1), mul(a);
37
    while(b){
38
        if(b & 1)ret = ret * mul % MOD;
39
        b >>= 1;
40
        mul = mul * mul % MOD;
41
    }return ret;
42
}
43

44
int N;
45
int mxdep;
46
int inv2;
47
int dep[310000];
48
int fa[310000];
49
ll ans(0);
50
ll sum[310000][21], sum2[310000][21];
51

52
ll DP(int p, int i){
53
    if(i == 1)return 1;
54
    return ((sum[p][i] * sum[p][i] % MOD - sum2[p][i]) % MOD + MOD) % MOD * inv2 % MOD;
55
}
56
void dfs(int p = 1, int fa = 0){
57
    dep[p] = dep[fa] + 1;
58
    for(auto i = head[p]; i; i = i->nxt)
59
        if(SON != fa)dfs(SON, p);
60
}
61

62
int main(){
63
    // freopen("in.txt", "r", stdin);
64
    // freopen("out.txt", "w", stdout);
65
    inv2 = qpow(2, MOD - 2);
66
    N = read();
67
    if(N == 1)printf("1\n"), exit(0);
68
    mxdep = (int)log2(N);
69
    for(int i = 2; i <= N; ++i){
70
        fa[i] = read();
71
        head[i] = new Edge{head[i], fa[i]};
72
        head[fa[i]] = new Edge{head[fa[i]], i};
73
    }dfs();
74
    for(int cp = 1; cp <= N; ++cp){
75
        if(dep[cp] <= mxdep){
76
            sum[cp][1] = sum2[cp][1] = 1;
77
            ll cnt(1), cur(cp), lst(-1), lstDP(0);
78
            while(cur != 1){
79
                lst = cur;
80
                cur = fa[cur], ++cnt;
81
                ll tmp = DP(cur, cnt);
82
                (((sum[cur][cnt] -= lstDP) %= MOD) += MOD) %= MOD;
83
                (((sum2[cur][cnt] -= lstDP * lstDP % MOD) %= MOD) += MOD) %= MOD;
84
                lstDP = tmp;
85
                (sum[cur][cnt] += DP(lst, cnt - 1)) %= MOD;
86
                (sum2[cur][cnt] += DP(lst, cnt - 1) * DP(lst, cnt - 1) % MOD) %= MOD;
87
            }
88
        }ans = 0;
89
        for(int i = 1; i <= mxdep; ++i)(ans += DP(1, i)) %= MOD;
90
        printf("%lld\n", ans);
91
    }
92
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
93
    return 0;
94
}
95

96
template < typename T >
97
inline T read(void){
98
    T ret(0);
99
    int flag(1);
100
    char c = getchar();
101
    while(c != '-' && !isdigit(c))c = getchar();
102
    if(c == '-')flag = -1, c = getchar();
103
    while(isdigit(c)){
104
        ret *= 10;
105
        ret += int(c - '0');
106
        c = getchar();
107
    }
108
    ret *= flag;
109
    return ret;
110
}

UPD

update-2023_01_03 初稿