题解：AT_agc070_b [AGC070B] Odd Namori

· · 题解

我嘞个容斥仙人啊！

首先这个 2^{\mathrm{cnt}} 就很奇妙，考虑赋予其一个组合意义：每个环要么选上，要么不选。注意到这里可以顺便容斥掉出现偶环的情况。具体地，选出一个偶环乘上 -1，选出一个奇环乘上 1，则存在奇环的图都会被我们容斥掉。

假设我们选出的环上的点的集合为 S，显然 1\in S，则剩下的点不能和父亲连边，有一个 (n-1)^{n-|S|} 的贡献，对于 1\notin S 可能需要特殊处理。

交换求和顺序，我们先钦定 S，考虑 S 内部的贡献 f(S)。

Lamma 1：如果不考虑树边，则 f(S)=[|S|=1]。

证明：

考虑构造双射：交换编号最小节点和编号最大节点的出边。

此时会有两个环合并成一个大的环，或者一个大环被拆成两个小环，偶环个数奇偶性必然改变。

所以若 |S|>1，则 2f(S)=0，进而 f(S)=0。

现在我们把没有考虑到的条件加回来。首先钦定的树边肯定是若干条链，把链缩起来后可以得到偶链和奇链，可以缩点成为奇点和偶点。稍加推理可以得到第二个重要性质。

Lamma 2：考虑树边的情况下，f(S)=1 当且仅当 S 是一个祖先后代链。

证明：

如果缩点后存在至少两个点，则 f(S)=0，所以现在只有一个点，并且和 S 有关的所有树边都需要被钦定。

如果这个点是偶点，则有奇数条被钦定的边；如果这个点是奇点，则有偶数条被钦定的边，所以总共有偶数个 -1 相乘，贡献为 -1。

所以我们只需要统计出长度为 d 的链有多少条，带入公式计算即可，时间复杂度线性。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9,mod=998244353;
int n,dep[N],tj[N];
int pw[N],ans;
signed main()
{
    scanf("%d",&n);
    for(int i=2,x;i<=n;i++) scanf("%d",&x),dep[i]=dep[x]+1;
    for(int i=1;i<=n;i++) tj[dep[i]]++;
    for(int i=n;i>=1;i--) (tj[i]+=tj[i+1])%=mod;
    pw[0]=1;
    for(int i=1;i<=n;i++) pw[i]=1ll*pw[i-1]*(n-1)%mod;
    ans=1ll*pw[n-1]*n%mod;
    for(int i=1;i<=n;i++) (ans+=pw[n-dep[i]-1])%=mod;
    for(int i=1;i<n;i++) (ans+=1ll*pw[n-i-1]*tj[i]%mod*n%mod)%=mod;
    (ans+=tj[n])%=mod;
    printf("%d\n",ans);
}