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

保存最终答案。

cnt=\sum_{i=1}^{maxn}dp_i

代码

注意：

要记得取模，同时注意做减法时要先加模数，防止出现负数。
多测要清空，但用 memset 会超时，所以使用 fill。

代码如下：

CPP

#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;
}

题解：CF2070D Tree Jumps

文章操作

CF2070D Tree Jumps 题解

题意

思路

代码

相关推荐

评论

题解：CF2070D Tree Jumps