CF543D 题解

前言

题目传送门！

更好的阅读体验？

比较有趣的换根 DP。

思路

First DFS

按照换根 DP 套路，先钦定 \(1\) 为首都（即根节点），并计算。

显然是树形 DP。设 \(dp_{u}\) 表示以 \(u\) 为根的子树全部满足的方案数。

对于一条树边 \((u, v)\)：

• 如果 \((u,v)\) 修，就意味着 \(v\) 对应子树的所有点，还有一次不修的机会，即 \(dp_v\)。
• 如果 \((u,v)\) 不修，没容错了，下面的全得修，就是 \(1\)。

综上，\(dp_u=\prod\limits_{\text{son}=v} dp_u \times (dp_v+1)\)。

Second DFS

进行换根。

假设当前根为 \(u\)。对于一条树边 \((u, v)\)，我们可以换根 \(\text{root}=v\)，那么：

• \(u\) 少了 \(v\) 原本的那个子树。相当于原本答案去除 \((dp_v+1)\) 这个分支，即除法（考虑逆元？）。
• \(v\) 多了 \(u\) 这个子树。同样的，相当于添加了 \((dp_u+1)\) 这个分支，即乘法。

按照上述转移就做完了。但是！由于 \(0\) 没有逆元，所以直接除不可取。使用前后缀积的方式快速维护，参考代码。

代码

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
struct Edge {int now, nxt;} e[N << 1];
int head[N], cur;
void add(int u, int v)
{
	e[++cur].now = v, e[cur].nxt = head[u];
	head[u] = cur;
}
int dp[N]; //dp[u] : 以u为根的方案数 
//如果(u,v)修，就是 dp[v]：如果(u,v)不修，下面的全得修，就是1。dp[u]=prod dp[u] * (dp[v]+1)
void dfs(int u, int fa)
{
	dp[u] = 1;
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].now;
		if (v == fa) continue;
		dfs(v, u), dp[u] = 1ll * dp[u] * (dp[v] + 1) % mod;
	}
}
#define update(x) pre.push_back(x + 1), suf.push_back(x + 1)
void DFS(int u, int fa, int mulfa)
{
	vector <int> pre, suf;
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].now;
		if (v == fa) {if (mulfa != -1) update(mulfa);}
		else update(dp[v]);
	}
	int siz = pre.size();
	
	#define lst(i) (i == 0 ? 1 : pre[i - 1])
	#define nxt(i) (i == siz - 1 ? 1 : suf[i + 1])
	for (int i = 0; i < siz; i++) pre[i] = 1ll * pre[i] * lst(i) % mod;
	for (int i = siz - 1; ~i; i--) suf[i] = 1ll * suf[i] * nxt(i) % mod;
	
	for (int i = head[u], pos = 0; i; i = e[i].nxt, pos++)
	{
		int v = e[i].now;
		if (v == fa) continue;
		int tmp = 1ll * lst(pos) * nxt(pos) % mod;
		dp[v] = 1ll * dp[v] * (tmp + 1) % mod, DFS(v, u, tmp);
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 2; i <= n; i++)
	{
		int u;
		scanf("%d", &u);
		add(i, u), add(u, i);
	}
	dfs(1, 0), DFS(1, 0, -1);
	for (int i = 1; i <= n; i++) printf("%d ", dp[i]);
	return 0;
}

希望能帮助到大家！