fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using vi = vector<int>;
  5. using ll = long long;
  6. using vl = vector<ll>;
  7. const ll mod = 998244353;
  8. const int N = 2e5 + 5;
  9. vl e[N];
  10. vl dp[3][N];
  11. ll solve(int u, int idx, int k){
  12.     if(e[u].size() == 0){
  13.         return 1;
  14.     }
  15.     if(idx == e[u].size()){
  16.         if(k == 1) return 0;
  17.         return 1;
  18.     }
  19.     ll& r = dp[k][u][idx];
  20.     if(r != -1) return r;
  21.     r = 0;
  22.     if(k == 0){ // don't need to return
  23.         // cut 
  24.         r += solve(e[u][idx], 0, 1) * solve(u, idx + 1, 0);
  25.         // don't cut
  26.         r += solve(e[u][idx], 0, 0) * solve(u, idx + 1, 0);
  27.     }else if(k == 1){  // need to return
  28.         // cut
  29.         r += solve(e[u][idx], 0, 1) * solve(u, idx + 1, 1);
  30.         // don't cut
  31.         r += solve(e[u][idx], 0, 1) * solve(u, idx + 1, 0);
  32.         // don't cut and don't return
  33.         r += solve(e[u][idx], 0, 2) * solve(u, idx + 1, 1);
  34.     }else{ // don't return
  35.         // cut
  36.         r += solve(e[u][idx], 0, 1) * solve(u, idx + 1, 2);
  37.         // don't cut
  38.         r += solve(e[u][idx], 0, 2) * solve(u, idx + 1, 2);
  39.     }
  40.     r %= mod;
  41.     return r;
  42. }
  43. int main(){
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(NULL);
  46.     int n;
  47.     cin >> n;
  48.     for(int i = 1; i < n; i++){
  49.         int u,v;
  50.         cin >> u >> v;
  51.         e[u].push_back(v);
  52.     }
  53.     for(int i = 1; i <= n; i++){
  54.         dp[0][i] = vl(e[i].size() + 5, -1);
  55.         dp[1][i] = vl(e[i].size() + 5, -1);
  56.         dp[2][i] = vl(e[i].size() + 5, -1);
  57.     }
  58.     cout << solve(1, 0, 0) << '\n';
  59. }
Success #stdin #stdout 0.01s 22280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/nyZQm3
language:
C++ (gcc 8.3)
created:
5 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!