fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pb push_back
  5. #define ii pair<int,int>
  6. #define all(x) x.begin(),x.end()
  7. #define fo(i, a, b) for (int i=(a),_b=(int)(b);i<=_b;++i)
  8. #define fd(i, a, b) for (int i=(a),_b=(int)(b);i>=_b;--i)
  9. #define umax(a, b) a=max(a, b)
  10. #define umin(a, b) a=min(a, b)
  11. #define ve vector
  12. #define vi ve<int>
  13. #define vl ve<ll>
  14. #define vvi ve<vi>
  15. #define ar array
  16. #define fi first
  17. #define se second
  18. const int N = 1e6+5, mod = 998244353;
  19.  
  20. template <const int32_t MOD>
  21. struct modint {
  22.   int32_t value;
  23.   modint() = default;
  24.   modint(int32_t value_) : value(value_) {}
  25.   inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
  26.   inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c <    0 ? c + MOD : c); }
  27.   inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
  28.   inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
  29.   inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
  30.   inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
  31.   inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
  32.   modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
  33.   modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
  34.   inline modint<MOD> operator /  (modint<MOD> other) const { return *this *  other.inv(); }
  35.   inline modint<MOD> operator /= (modint<MOD> other)       { return *this *= other.inv(); }
  36.   inline bool operator == (modint<MOD> other) const { return value == other.value; }
  37.   inline bool operator != (modint<MOD> other) const { return value != other.value; }
  38.   inline bool operator < (modint<MOD> other) const { return value < other.value; }
  39.   inline bool operator > (modint<MOD> other) const { return value > other.value; }
  40. };
  41. template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
  42. template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
  43. template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
  44. template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }
  45.  
  46. using mint = modint<mod>;
  47.  
  48. int n, h[N], fa[N];
  49. ve<int> g[N];
  50. mint dp[N], dp1[N];
  51. bool vis[N];
  52.  
  53. void sol(int tc) {
  54.     cin >> n;
  55.     fo(i,1,n) g[i].clear(), dp[i] = dp1[i] = vis[i] = 0;
  56.     fo(i,2,n) {
  57.         int p; cin >> p;
  58.         fa[i] = p;
  59.         g[i].pb(p), g[p].pb(i);
  60.     }
  61.     queue<int> q; q.push(1); vis[1] = 0;
  62.     while (q.size()) {
  63.         int u = q.front(); q.pop();
  64.         for (int v : g[u]) if (!vis[v]) {
  65.             q.push(v);
  66.             vis[v] = 1;
  67.             h[v] = h[u] + 1;
  68.         }
  69.         if (u == 1) continue;
  70.         else if (fa[u] == 1) {
  71.             dp[u] = 1;
  72.         } else {
  73.             dp[u] = dp1[h[u]-1] - dp[fa[u]];
  74.         }
  75.         dp1[h[u]] += dp[u];
  76.     }
  77.     mint ans = 1;
  78.     fo(i,1,n) ans += dp[i];
  79.     cout << ans << '\n';
  80. }
  81.  
  82. signed main() {
  83.     cin.tie(0) -> sync_with_stdio(0);
  84.     if (fopen("A.inp", "r")) freopen("A.inp", "r", stdin);
  85.     int tc = 1; cin >> tc;
  86.     fo(i,1,tc) sol(i);
  87. }
  88.  
Success #stdin #stdout 0.01s 28156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/wTbRwJ
language:
C++ (gcc 8.3)
created:
10 days 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!