Language: C++

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define SZ(a) ((int)(a).size())
#define ALL(a) a.begin(), a.end()
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia

template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

inline int read() {
    static int _, __; static char c_;
    for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
    for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
    return _ * __;
}

const int maxn = 2e5 + 5, MOD = 1e9 + 7;

int n, fa[19][maxn], v[maxn], nex[maxn], beg[maxn], e, v_[maxn], nex_[maxn], beg_[maxn], e_, dfn[maxn], clk, dep[maxn], dp[maxn][2], stk[maxn], top, Ans, sz[maxn];
vector<int> vec[maxn];

inline void add(int uu, int vv) { v[++ e] = vv, nex[e] = beg[uu], beg[uu] = e; }
inline void add_(int uu, int vv) { v_[++ e_] = vv, nex_[e_] = beg_[uu], beg_[uu] = e_; }
inline int  ad(int x, int y) { if ((x += y) >= MOD) return x - MOD; return x; }
inline int  Pow(int a, int b) {
    static int Ans;
    for (Ans = 1; b; b >>= 1, a = (LL)a * a % MOD) if (b & 1) Ans = (LL)Ans * a % MOD;
    return Ans;
}

void DFS(int u) {
    vec[dep[u]].pb(u), dfn[u] = ++ clk;
    For(i, 1, 17) fa[i][u] = fa[i - 1][fa[i - 1][u]];
    for (register int i = beg[u]; i; i = nex[i])
        dep[v[i]] = dep[u] + 1, DFS(v[i]);
}

inline int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    Fordown(i, 17, 0) if (dep[fa[i][u]] >= dep[v]) u = fa[i][u];
    if (u == v) return u;
    Fordown(i, 17, 0) if (fa[i][u] ^ fa[i][v]) u = fa[i][u], v = fa[i][v];
    return fa[0][u];
}

inline bool cmp(int x, int y) { return dfn[x] < dfn[y]; }

void DP(int u) {
    if (!beg_[u]) { dp[u][0] = dp[u][1] = sz[u] = 1; return; }
    sz[u] = 0;
    int prod = 1;
    for (register int i = beg_[u]; i; i = nex_[i])
        DP(v_[i]), prod = (LL)prod * dp[v_[i]][0] % MOD, sz[u] += sz[v_[i]];
    dp[u][1] = 0;
    for (register int i = beg_[u]; i; i = nex_[i])
        dp[u][1] = ad(dp[u][1], (LL)dp[v_[i]][1] * Pow(dp[v_[i]][0], MOD - 2) % MOD * prod % MOD);
    dp[u][0] = ad(Pow(2, sz[u]), MOD - dp[u][1]), beg_[u] = 0;
}

int main()
{
#ifdef hany01
    freopen("arc086e.in", "r", stdin);
    freopen("arc086e.out", "w", stdout);
#endif

    n = read() + 1;
    For(i, 2, n) fa[0][i] = read() + 1, add(fa[0][i], i);
    dep[1] = 1, DFS(1);

    for (register int dpt = 1, sz; ; ++ dpt) {
        if (!(sz = SZ(vec[dpt]))) break;
        sort(ALL(vec[dpt]), cmp), stk[top = 1] = 1, e_ = 0;
        For(i, vec[dpt][0] == 1, sz - 1) {
            register int lca = LCA(vec[dpt][i], stk[top]);
            if (lca != stk[top]) {
                while (top > 1 && dep[stk[top - 1]] >= dep[lca]) add_(stk[top - 1], stk[top]), -- top;
                if (stk[top] != lca) add_(lca, stk[top]), stk[top] = lca;
            }
            stk[++ top] = vec[dpt][i];
        }
        Fordown(i, top, 2) add_(stk[i - 1], stk[i]);
        DP(1), Ans = ad(Ans, (LL)dp[1][1] * Pow(2, n - sz) % MOD);
    }
    printf("%d\n", Ans);

    return 0;
}
--------------------- 
作者：Hany01 
来源：CSDN 
原文：https://blog.csdn.net/hhaannyyii/article/details/82052464 
版权声明：本文为博主原创文章，转载请附上博文链接！

Compiler output:
a.cc: In function 'void DFS(int)':
a.cc:50:9: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   50 |     For(i, 1, 17) fa[i][u] = fa[i - 1][fa[i - 1][u]];
      |         ^
a.cc:9:40: note: in definition of macro 'For'
    9 | #define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
      |                                        ^
a.cc:50:9: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   50 |     For(i, 1, 17) fa[i][u] = fa[i - 1][fa[i - 1][u]];
      |         ^
a.cc:9:49: note: in definition of macro 'For'
    9 | #define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
      |                                                 ^
a.cc:51:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   51 |     for (register int i = beg[u]; i; i = nex[i])
      |                       ^
a.cc: In function 'int LCA(int, int)':
a.cc:57:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   57 |     Fordown(i, 17, 0) if (dep[fa[i][u]] >= dep[v]) u = fa[i][u];
      |             ^
a.cc:10:44: note: in definition of macro 'Fordown'
   10 | #define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
      |                                            ^
a.cc:57:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   57 |     Fordown(i, 17, 0) if (dep[fa[i][u]] >= dep[v]) u = fa[i][u];
      |             ^
a.cc:10:53: note: in definition of macro 'Fordown'
   10 | #define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
      |                                                     ^
a.cc:59:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   59 |     Fordown(i, 17, 0) if (fa[i][u] ^ fa[i][v]) u = fa[i][u], v = fa[i][v];
      |             ^
a.cc:10:44: note: in definition of macro 'Fordown'
   10 | #define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
      |                                            ^
a.cc:59:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   59 |     Fordown(i, 17, 0) if (fa[i][u] ^ fa[i][v]) u = fa[i][u], v = fa[i][v];
      |             ^
a.cc:10:53: note: in definition of macro 'Fordown'
   10 | #define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
      |                                                     ^
a.cc: In function 'void DP(int)':
a.cc:69:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   69 |     for (register int i = beg_[u]; i; i = nex_[i])
      |                       ^
a.cc:72:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   72 |     for (register int i = beg_[u]; i; i = nex_[i])
      |                       ^
a.cc: In function 'int main()':
a.cc:85:9: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   85 |     For(i, 2, n) fa[0][i] = read() + 1, add(fa[0][i], i);
      |         ^
a.cc:9:40: note: in definition of macro 'For'
    9 | #define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
      |                                        ^
a.cc:85:9: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   85 |     For(i, 2, n) fa[0][i] = read() + 1, add(fa[0][i], i);
      |         ^
a.cc:9:49: note: in definition of macro 'For'
    9 | #define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
      |                                                 ^
a.cc:88:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   88 |     for (register int dpt = 1, sz; ; ++ dpt) {
      |                       ^~~
a.cc:88:32: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   88 |     for (register int dpt = 1, sz; ; ++ dpt) {
      |                                ^~
a.cc:91:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   91 |         For(i, vec[dpt][0] == 1, sz - 1) {
      |             ^
a.cc:9:40: note: in definition of macro 'For'
    9 | #define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
      |                                        ^
a.cc:91:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   91 |         For(i, vec[dpt][0] == 1, sz - 1) {
      |             ^
a.cc:9:49: note: in definition of macro 'For'
    9 | #define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
      |                                                 ^
a.cc:92:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   92 |             register int lca = LCA(vec[dpt][i], stk[top]);
      |                          ^~~
a.cc:99:17: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   99 |         Fordown(i, top, 2) add_(stk[i - 1], stk[i]);
      |                 ^
a.cc:10:44: note: in definition of macro 'Fordown'
   10 | #define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
      |                                            ^
a.cc:99:17: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   99 |         Fordown(i, top, 2) add_(stk[i - 1], stk[i]);
      |                 ^
a.cc:10:53: note: in definition of macro 'Fordown'
   10 | #define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
      |                                                     ^
a.cc: At global scope:
a.cc:106:1: error: expected unqualified-id before '--' token
  106 | ---------------------
      | ^~