题解：CF2070D Tree Jumps

Tomwsc · 2025-03-04 21:06:39 · 题解

CF2070D Tree Jumps 题解

题意

有点难表述，直接传送吧。

思路

一开始看错题目，调了半天。

一道比较水的 dp。

由题意可得：若 u 可以跳到 v，则 v 的深度和 u 相差 1。于是便可以想到用 depth 数组记录每个节点的深度。同时，由于 v 和 u 的关系不能为父子节点，于是便可以令人想到用一个数组 more 来记录以每个节点结尾的序列总数。这样在转移时，便可以用总数来减掉不能算的 more_u。

设 dp_i 表示以第 i 层的节点结尾的序列总数。假设现在转移到 v 节点，其父亲为 u 节点，则可以得到：

• depth_v=depth_u+1
• dp_{depth_v}=dp_{depth_v}+dp_{depth_u}-more_u
• more_v=dp_{depth_u}-more_u

因为序列可以以任意深度的节点结尾，所以有最终答案便是各深度 dp 的值之和，即：

设最大深度为 maxn，cnt 保存最终答案。

代码

注意：

• 要记得取模，同时注意做减法时要先加模数，防止出现负数。

• 多测要清空，但用 memset 会超时，所以使用 fill。

代码如下：

#include<bits/stdc++.h>
#define inf (1ll << 62)
#define regint register int
using namespace std;
const int MAXN = 3e5 + 10 , mod = 998244353;
int t , n;
int depth[MAXN] , dp[MAXN] , more[MAXN];
vector<int>G[MAXN];
struct Node {
    int u , fa;
};

inline void bfs() {
    queue<Node>q;
    q.push({1 , 0});
    depth[1] = 1;
    dp[1] = 1;
    while(!q.empty()) {
        int u = q.front().u;
        int fa = q.front().fa;
        q.pop();
        for(auto v : G[u]) {
            if(v == fa)
                continue;
            depth[v] = depth[u] + 1;
            dp[depth[v]] = ((dp[depth[v]] + dp[depth[u]]) % mod + mod - more[u]) % mod;
            more[v] = (dp[depth[u]] + mod - more[u]) % mod;
            q.push({v , u});
        }
    }
    return;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t --) {
        cin >> n; 
        for(regint i = 1;i <= n;i ++)
            G[i].clear();
        fill(depth + 1 , depth + 1 + n , 0);
        fill(dp + 1 , dp + 1 + n , 0);
        fill(more + 1 , more + 1 + n , 0);
        for(regint i = 2;i <= n;i ++) {
            int u;
            cin >> u;
            G[u].push_back(i);
            G[i].push_back(u);
        }
        bfs();
        int cnt = 0;
        for(regint i = n;i >= 1;i --)
            cnt = (cnt + dp[i]) % mod;
        cout << cnt << '\n';
    }
    return 0;
}