fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 200005;
  6. const long long MOD0 = 998244353;
  7. const long long MOD1 = 998244352; // phi(MOD0) = 2^23 * 7 * 17
  8. const long long MOD2 = 402653184; // phi(MOD1) = 3 * 2^27
  9. const long long MOD3 = 67108864;  // phi(2^27) = 2^26 (ước của MOD2)
  10. const long long INV2 = (MOD0 + 1) / 2;
  11.  
  12. int n;
  13. int parent_node[MAXN];
  14. bool has_child[MAXN];
  15. long long k1[MAXN]; // K(u) mod MOD1
  16. long long k2[MAXN]; // K(u) mod MOD2
  17.  
  18. long long powerMod(long long base, long long exp, long long mod) {
  19.     long long res = 1;
  20.     base %= mod;
  21.     while (exp > 0) {
  22.         if (exp & 1) {
  23.             res = (res * base) % mod;
  24.         }
  25.         base = (base * base) % mod;
  26.         exp >>= 1;
  27.     }
  28.     return res;
  29. }
  30.  
  31. void input() {
  32.     cin >> n;
  33.     for (int i = 2; i <= n; ++i) {
  34.         cin >> parent_node[i];
  35.         has_child[parent_node[i]] = true;
  36.     }
  37. }
  38.  
  39. void solve() {
  40.     long long ans = 0;
  41.  
  42.     // Duyệt ngược từ N về 2 (đảm bảo mọi đỉnh con đều được tính trước đỉnh cha vì p_i < i)
  43.     for (int u = n; u >= 2; --u) {
  44.         long long a0, a1, a2;
  45.  
  46.         if (!has_child[u]) {
  47.             // u là lá => K(u) = 0 => 3^{K(u)} = 1
  48.             a0 = 1;
  49.             a1 = 1;
  50.             a2 = 1;
  51.         } else {
  52.             // u không phải lá => K(u) >= 1
  53.             a0 = powerMod(3, k1[u], MOD0);
  54.             a1 = powerMod(3, k2[u], MOD1);
  55.             long long exp2 = (k2[u] - 1 + MOD3) % MOD3 + 1;
  56.             a2 = powerMod(3, exp2, MOD2);
  57.         }
  58.  
  59.         // Cộng số nhát chém để triệt tiêu các con của u: (3^{K(u)} - 1) / 2
  60.         long long cuts_u = (a0 - 1 + MOD0) % MOD0 * INV2 % MOD0;
  61.         ans = (ans + cuts_u) % MOD0;
  62.  
  63.         int p = parent_node[u];
  64.         if (p == 1) {
  65.             // Nếu cha là gốc 1, đóng góp 3^{K(u)} vào K(1) (cũng chính là số nhát chém ở độ sâu 1)
  66.             ans = (ans + a0) % MOD0;
  67.         } else {
  68.             k1[p] = (k1[p] + a1) % MOD1;
  69.             k2[p] = (k2[p] + a2) % MOD2;
  70.         }
  71.     }
  72.  
  73.     cout << ans << "\n";
  74. }
  75.  
  76. int main() {
  77.     ios_base :: sync_with_stdio (false);
  78.     cin.tie (0);
  79.     cout.tie (0);
  80.  
  81.     input();
  82.     solve();
  83.  
  84.     return 0;
  85. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/9GC3IN
language:
C++14 (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!