Code:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 200004
#define mod 998244353
#define ll long long
using namespace std;
inline ll add(ll a,ll b) {
return (a+b)%mod;
}
inline ll de(ll a,ll b) {
return ((a%mod)-(b%mod)+mod)%mod;
}
int n,edges;
int hd[maxn],to[maxn],nex[maxn],dep[maxn],f[maxn],siz[maxn],son[maxn],top[maxn],p[maxn],sz[maxn];
ll inv[maxn],mul,g[maxn],ans;
struct Node {
int u,v;
Node(int u=0,int v=0):u(u),v(v){}
};
vector<Node>vi[maxn];
vector<int>G[maxn];
ll qpow(ll base,ll k) {
ll re=1;
while(k) {
if(k&1) re=re*base%mod;
base=base*base%mod;
k>>=1;
}
return re;
}
void add(int u,int v) {
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void dfs1(int u) {
dep[u]=dep[f[u]]+1,siz[u]=1,G[dep[u]].push_back(u);
for(int i=hd[u];i;i=nex[i]) {
int v=to[i];
if(v==f[u]) continue;
dfs1(v),siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int tp) {
top[u]=tp;
if(son[u]) dfs2(son[u],tp);
for(int i=hd[u];i;i=nex[i]) {
int v=to[i];
if(v==f[u]||v==son[u]) continue;
dfs2(v,v);
}
}
int LCA(int x,int y) {
while(top[x]^top[y]) {
dep[top[x]]>dep[top[y]]?x=f[top[x]]:y=f[top[y]];
}
return dep[x]<dep[y]?x:y;
}
void init() {
for(int i=0;i<maxn;++i) p[i]=i,sz[i]=1;
}
int find(int x) {
return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x,int y) {
int fx=find(x),fy=find(y);
if(fx!=fy) {
mul=mul*inv[sz[fx]+1]%mod*inv[sz[fy]+1]%mod;
p[fx]=fy, sz[fy]+=sz[fx];
mul=mul*(sz[fy]+1)%mod;
}
}
void Initialize() {
init(),inv[1]=1,mul=qpow(2,n);
for(int i=2;i<maxn;++i) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
}
int main() {
// setIO("input");
scanf("%d",&n);
for(int i=2;i<=n;++i) scanf("%d",&f[i]), add(f[i],i);
Initialize(),dfs1(1),dfs2(1,1);
for(int i=2;i<=n;++i) vi[dep[i]-1].push_back(Node(i,f[i]));
for(int i=1;i<=n;++i) {
for(int j=1;j<G[i].size();++j) {
vi[dep[G[i][j]] - dep[LCA(G[i][j], G[i][j-1])]].push_back(Node(G[i][j], G[i][j-1]));
}
}
ans=de(mul,n+1);
for(int i=1;i<=n;++i) {
for(int j=0;j<vi[i].size();++j)
merge(vi[i][j].u, vi[i][j].v);
ans=add(ans,de(mul,n+1));
}
printf("%lld\n",ans);
return 0;
}

  

最新文章

  1. PHPCMS_V9 模型字段添加单文件上传功能
  2. objective-c系列-NSDictionary&amp;NSMutableDictionary
  3. java笔记--关于线程通信
  4. 慕课网-安卓工程师初养成-2-5 如何命名Java变量
  5. regular expression 基本语法
  6. js Function 加不加new 详解
  7. js 实现倒计时效果
  8. Struts2(五)常量的配置
  9. LeetCode之“数学”:Plus One
  10. codeforces#983 B. XOR-pyramid (dp)
  11. 学生成绩管理系统3.0(JSP+Servlet+MySQL)
  12. Java集合之LinkedHashMap源码分析
  13. Kubernetes 核心概念
  14. Excel--数据对比方法
  15. PHP企业微信授权
  16. Spring @Value注入值失败,错误信息提示:Could not resolve placeholder
  17. BZOJ.4939.[Ynoi2016]掉进兔子洞(莫队 bitset 分组询问)
  18. shell 循环语句
  19. RhinoMock初探
  20. ES6的新特性(20)—— Module 的加载实现

热门文章

  1. redis4支持内存碎片清理功能使用
  2. 【HANA系列】SAP HANA日期函数总结
  3. 【Qt开发】Qt标准对话框之QMessageBox
  4. Canvas入门05-渐变颜色
  5. vue组件注册(极客时间Vue视频笔记)
  6. [DS+Algo] 002 一维表结构
  7. 关于Logcat
  8. sqlplus无法登陆?
  9. [CF585E]Marbles
  10. swtich和case语句中,定义变量要加花括号