[ABC264Ex] Perfect Binary Tree

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}=sumlimits_{v1in son}sumlimits_{v2>v1,v2in son}dp_{v1,j-1}times dp_{v2,j-1}$$

这个可以化简为 $$(sumlimits_{vin son}dp_{v,j-1})^2-sumlimits_{vin son}dp_{v,j-1}^2$$

这个东西就可以实现树上 (O(1)) 转移了，最终答案为 (sumlimits_{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("%lldn",ans);
	}
}

程序员灯塔
转载请注明原文链接：[ABC264Ex] Perfect Binary Tree