Submission #32681890

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

vector<int> G[200010];

int main() {
  int n = read();
  rep(i,1,n){
    int u = read() - 1;
    int v = read() - 1;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  vector<int> fa(n,-1); // 父节点?
  vector<int> order={0}; // 树上bfs 顺序, 反序就是树上dp
  rep(i,0,n) {
    int u = order[i];
    for(auto v:G[u]){
      if(v == fa[u]) continue;
      fa[v] = u;
      order.push_back(v);
    }
  }

  vector<vector<ll>> dp(n,vector<ll>(4));
  per(i,0,n){
    int u = order[i];
    dp[u][1] = 1;
    ll all0 = 1;
    ll all3 = 1;
    ll pre1 = 0;
    for(auto v:G[u]){
      if(fa[v]!=u) continue;
      ll s12 = (dp[v][1]+dp[v][2])%MOD;
      // 0
      dp[u][0] = (dp[u][0] * dp[v][0] % MOD + all0 * s12 % MOD)%MOD;
      // 2
      dp[u][2] = (dp[u][2] * dp[v][3] % MOD + all3 * s12 % MOD)%MOD;

      dp[u][3] = (dp[u][3] * dp[v][3] % MOD + pre1 * s12 % MOD)%MOD;
      pre1     = (pre1     * dp[v][3] % MOD + all3 * s12 % MOD) %MOD;

      (all0 *= dp[v][0]) %= MOD;
      (all3 *= dp[v][3]) %= MOD;
    }
    // 1
    dp[u][1] = all0;
    (dp[u][3] *= 2) %= MOD;
  }
  printf("%lld\n",(dp[0][0] * 2 % MOD + dp[0][3])%MOD);
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:10:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   10 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

Judge Result