标签：Perfect Binary int 题解 ll ret 节点 dp MOD

[ABC264Ex] Perfect Binary Tree Solution

目录

• [ABC264Ex] Perfect Binary Tree Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

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

Solution

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

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

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

\[dp(p, i) = \sum_{u \lt v, u, v \in son_p} dp(u, i - 1) \times dp(v, i - 1) \]

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

\[dp(p, i) = \dfrac{1}{2}((\sum_{u \in son_p}dp(u, i - 1))^2 - \sum_{u \in son_p}dp(u, i - 1)^2) \]

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

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

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

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD (998244353ll)

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

struct Edge{
    Edge* nxt;
    int to;
    OPNEW;
}ed[610000];
ROPNEW(ed);
Edge* head[310000];

ll qpow(ll a, ll b){
    ll ret(1), mul(a);
    while(b){
        if(b & 1)ret = ret * mul % MOD;
        b >>= 1;
        mul = mul * mul % MOD;
    }return ret;
}

int N;
int mxdep;
int inv2;
int dep[310000];
int fa[310000];
ll ans(0);
ll sum[310000][21], sum2[310000][21];

ll DP(int p, int i){
    if(i == 1)return 1;
    return ((sum[p][i] * sum[p][i] % MOD - sum2[p][i]) % MOD + MOD) % MOD * inv2 % MOD;
}
void dfs(int p = 1, int fa = 0){
    dep[p] = dep[fa] + 1;
    for(auto i = head[p]; i; i = i->nxt)
        if(SON != fa)dfs(SON, p);
}

int main(){
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    inv2 = qpow(2, MOD - 2);
    N = read();
    if(N == 1)printf("1\n"), exit(0);
    mxdep = (int)log2(N);
    for(int i = 2; i <= N; ++i){
        fa[i] = read();
        head[i] = new Edge{head[i], fa[i]};
        head[fa[i]] = new Edge{head[fa[i]], i};
    }dfs();
    for(int cp = 1; cp <= N; ++cp){
        if(dep[cp] <= mxdep){
            sum[cp][1] = sum2[cp][1] = 1;
            ll cnt(1), cur(cp), lst(-1), lstDP(0);
            while(cur != 1){
                lst = cur;
                cur = fa[cur], ++cnt;
                ll tmp = DP(cur, cnt);
                (((sum[cur][cnt] -= lstDP) %= MOD) += MOD) %= MOD;
                (((sum2[cur][cnt] -= lstDP * lstDP % MOD) %= MOD) += MOD) %= MOD;
                lstDP = tmp;
                (sum[cur][cnt] += DP(lst, cnt - 1)) %= MOD;
                (sum2[cur][cnt] += DP(lst, cnt - 1) * DP(lst, cnt - 1) % MOD) %= MOD;
            }
        }ans = 0;
        for(int i = 1; i <= mxdep; ++i)(ans += DP(1, i)) %= MOD;
        printf("%lld\n", ans);
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2023_01_03 初稿

标签：Perfect,Binary,int,题解,ll,ret,节点,dp,MOD
From： https://www.cnblogs.com/tsawke/p/17032813.html