题解：AT_agc070_b [AGC070B] Odd Namori

· · 题解

更好的阅读体验

太牛了。

一个好图是一个只有奇环的内基环树森林。我们要求的是所有好图中，2^{\text{cycle}} 之和。也就是说，对于一个图，初始贡献是 1，枚举它的每一个环，如果点数为奇数就让贡献 \times 2，点数为偶数就让贡献 \times 0 归零。

但还是不好算。我们把 2 写成 1 + 1，0 写成 1 + (-1)，就变成算上 1 的初始贡献，遇到奇环就 \times 1，遇到偶环就 \times -1，也就是加入一个环 S 我们就乘上 (-1)^{|S|+1} 的容斥系数，就能将偶环容斥掉。

我们先假设没有不能选树边的限制，考虑在一个点集 S 内部选环产生的贡献。

首先当 |S| = 1 时，只能连成一个自环，大小是奇数，因此贡献为 1。

接下来考虑一个非常逆天的双射：将 S 中元素用 1 \sim |S| 重标号，取出 1, 2 两个点交换其出边。

不难看出，偶环数量为奇数的权值和偶环数量为偶数的权值互为相反数！所以当 |S| > 1，会产生 0 的贡献。

接下来考虑加上限制后怎么做。连边等价与缩点，我们可以将一个点并到他的父亲上形成若干条链。

但是由于我们上面说了，要产生贡献当且仅当 |S| = 1，因此缩起的点一定只能是单独的一条子孙后代链。

那么我们考虑实现。我们首先要先将答案加上连边的方案总数 (n-1)^{n-1} \times n，因为我们是在 1 的基础上 \pm 1。接着我们要考虑一端为根的方案数。这个也很简单，假设我选择的点深度为 d，则深度最大的点确定后，一整条祖先后代链也确定了，剩下的点不选父亲就行了，因此方案数为 (n-1)^{n-d-1}。剩下的我们要数树上长度 =d 的链有多少条，把深度扔到桶里做后缀和即可，带入上式计算。

那么这道题就做完了，复杂度 O(n)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 100006
#define MOD 998244353
using namespace std;
int n,dep[N],t[N],pw[N],ans;
vector<int> G[N];
inline void add(int &x,int y){x+=y,x-=x>=MOD?MOD:0;}
void dfs(int u){for(int v:G[u])t[dep[v]=dep[u]+1]++,dfs(v);}
main()
{
    scanf("%lld",&n),pw[0]=1;
    for(int i=1;i<N;i++)pw[i]=pw[i-1]*(n-1)%MOD;
    for(int i=2,fa;i<=n;i++)
        scanf("%lld",&fa),G[fa].push_back(i);
    dfs(1),ans=pw[n-1]*n%MOD;
    for(int i=n;i;i--)add(t[i],t[i+1]);
    for(int i=1;i<=n;i++)add(ans,pw[n-dep[i]-1]);
    for(int i=1;i<n;i++)add(ans,t[i]*pw[n-i-1]%MOD*n%MOD);
    printf("%lld\n",ans);
    return 0;
}