[ABC264Ex] Perfect Binary Tree

标签：Perfect Binary le when tree Sample ge ABC264Ex dp

Problem Statement

We have a rooted tree with $N$ vertices numbered $1,2,\dots,N$.
The tree is rooted at Vertex $1$, and the parent of Vertex $i \ge 2$ is Vertex $P_i(<i)$.
For each integer $k=1,2,\dots,N$, solve the following problem:

There are $2^{k-1}$ ways to choose some of the vertices numbered between $1$ and $k$ so that Vertex $1$ is chosen.
How many of them satisfy the following condition: the subgraph induced by the set of chosen vertices forms a perfect binary tree (with $2^d-1$ vertices for a positive integer $d$) rooted at Vertex $1$?
Since the count may be enormous, print the count modulo $998244353$.

What is an induced subgraph?

Let $S$ be a subset of the vertex set of a graph $G$. The subgraph $H$ induced by this vertex set $S$ is constructed as follows:

Let the vertex set of $H$ equal $S$.
Then, we add edges to $H$ as follows:

For all vertex pairs $(i, j)$ such that $i,j \in S, i < j$, if there is an edge connecting $i$ and $j$ in $G$, then add an edge connecting $i$ and $j$ to $H$.

What is a perfect binary tree?

A perfect binary tree is a rooted tree that satisfies all of the following conditions:

Every vertex that is not a leaf has exactly $2$ children.
All leaves have the same distance from the root.

Here, we regard a graph with $1$ vertex and $0$ edges as a perfect binary tree, too.

Constraints

All values in input are integers.
$1 \le N \le 3 \times 10^5$
$1 \le P_i < i$

Input

Input is given from Standard Input in the following format:

$N$
$P_2$ $P_3$ $\dots$ $P_N$

Output

Print $N$ lines. The $i$-th ($1 \le i \le N$) line should contain the answer as an integer when $k=i$.

Sample Input 1

10
1 1 2 1 2 5 5 5 1

Sample Output 1

The following ways of choosing vertices should be counted:

$\{1\}$ when $k \ge 1$
$\{1,2,3\}$ when $k \ge 3$
$\{1,2,5\},\{1,3,5\}$ when $k \ge 5$
$\{1,2,4,5,6,7,8\}$ when $k \ge 8$
$\{1,2,4,5,6,7,9\},\{1,2,4,5,6,8,9\}$ when $k \ge 9$
$\{1,2,10\},\{1,3,10\},\{1,5,10\}$ when $k = 10$

Sample Input 2

Sample Output 2

If $N=1$, the $2$-nd line of the Input is empty.

Sample Input 3

10
1 2 3 4 5 6 7 8 9

Sample Output 3

Sample Input 4

13
1 1 1 2 2 2 3 3 3 4 4 4

Sample Output 4

先考虑如果不带实时询问怎么做？定义 $dp_{i,j}$ 为以 $i$ 为节点，深度为 $j$ 的导出完全二叉树有多少个。发现 $j$ 是 $logn$ 级别的，因为一个 $j$ 层完全二叉树的节点数量是 $2^j$ 级别，而节点数量要 $\le n$。

用 $son$ 表示 $i$ 的所有儿子的集合，初始化 $dp_{i,0}=1$$$dp_{i,j}=\sum\limits_{v1\in son}\sum\limits_{v2>v1,v2\in son}dp_{v1,j-1}\times dp_{v2,j-1}$$

这个可以化简为 $$(\sum\limits_{v\in son}dp_{v,j-1})^2-\sum\limits_{v\in son}dp_{v,j-1}^2$$

这个东西就可以实现树上 $O(1)$ 转移了，最终答案为 $\sum\limits_{j=0}^{logn}dp_{1,j}$，总复杂度 $O(nlogn)$

现在要求加点，询问。那么思路很简单，首先如果一个点的层数大过 $logn$，他影响不到答案。然后考虑不断往上爬，去更改会改变的答案。

要直接维护 $dp$ 值不容易，考虑维护所有 $dp$ 值的和还有平方和，有这两个更改我们可以推出 $dp$ 值的更改。然后发现，如果现在加入点 $x$ 的时候，点 $y$ 与点 $x$ 的层数差为 $a$，那么只有 $dp_{y,a}$ 有可能更改，加上 $x$ 的层数 $\le logn$，所以这样子改的复杂度是 $O(logn)$ 的。具体更改时就是减去旧的加上新的就行了。

#include<cstdio>
const int N=3e5+5,P=998244353,inv2=499122177;
typedef long long LL;
long long s[N][25],f[N][25],dp[N][25],ans,dep[N];//s表示和，f表示平方和 
int n,k,fa[N];
void dfs(int x,int y,LL a,LL b)//a表示原来的，b表示新的 
{
	LL k=dp[x][y];
	(s[x][y]+=b-a+P)%=P; 
	(f[x][y]+=b*b%P-a*a%P+P)%=P;
	dp[x][y]=(s[x][y]*s[x][y]%P-f[x][y]+P)*inv2%P;
	if(x-1)
		dfs(fa[x],y+1,k,dp[x][y]);
}
int main()
{
	scanf("%d",&n);
	dp[1][0]=1;
	puts("1");
	for(int i=2;i<=n;i++)
	{
		scanf("%d",fa+i),dep[i]=dep[fa[i]]+1;
		f[i][0]=dp[i][0]=s[i][0]=1;
		if(dep[i]<=20)
			dfs(fa[i],1,0,1);
//		puts("qzmakioi");
		ans=0;
		for(int j=0;j<=20;j++)
			(ans+=dp[1][j])%=P;
		printf("%lld\n",ans);
	}
}

标签：Perfect,Binary,le,when,tree,Sample,ge,ABC264Ex,dp
From： https://www.cnblogs.com/mekoszc/p/17001612.html