提出 #11958953

---

ソースコード 拡げる

#include <bits/stdc++.h>
typedef long long int ll;

using namespace std;

ll N, M;
vector<int> edge[200000];
ll dp[200000];
ll dp2[200000];
map<ll, map<ll,ll>> dp3;

void dfs(int cur, int par) {
  ll x = 1;
  for (auto c : edge[cur]) {
    if (c == par) continue;
    dfs(c, cur);
    x *= dp[c] + 1;
    x %= M;
  }
  dp[cur] = x;
}

void dfs2(int cur, int par) {
  ll x = 1;
  if (par != -1) {
    x *= (dp3[par][cur] + 1);
    x %= M;
  }
  for (auto c : edge[cur]) {
    if (c == par) continue;
    dfs2(c, cur);
    x *= dp[c] + 1;
    x %= M;
  }
  dp2[cur] = x;
}

ll prefix[200000];
ll suffix[200000];

void dfs3(int par, int ppar) {
  ll N = edge[par].size();
  if (N > 0) {
    prefix[0] = 1;
    if (edge[par][0] != ppar) prefix[0] = dp[edge[par][0]] + 1;
    for (int i=1; i<N; i++) {
      ll cur = edge[par][i];
      prefix[i] = prefix[i-1];
      if (cur != ppar) prefix[i] *= dp[cur] + 1;
      prefix[i] %= M;
    }

    suffix[N-1] = 1;
    if (edge[par][N-1] != ppar) suffix[N-1] = dp[edge[par][N-1]] + 1;
    for (int i=N-2; i>=0; i--) {
      ll cur = edge[par][i];
      suffix[i] = suffix[i+1];
      if (cur != ppar) suffix[i] *= dp[cur] + 1;
      suffix[i] %= M;
    }
  }
  // for (int i=0; i<N; i++) {
  //   printf("par=%ld i=%ld prefix=%ld suffix=%ld dp[edge[par][i]]=%ld\n", par, i, prefix[i], suffix[i], dp[edge[par][i]]);
  // }
  for (int i=0; i<edge[par].size(); i++) {
    ll cur = edge[par][i];
    if (cur == ppar) continue;
    ll x = 1;
    if (ppar != -1) {
      x *= (dp3[ppar][par] + 1) % M;
    }
    if (i-1 >= 0) { x *= prefix[i-1]; x %= M;}
    if (i+1 < N)  { x *= suffix[i+1]; x %= M;}
    dp3[par][cur] = x;
   //  printf("N=%d i=%d par=%ld cur=%ld dp3[par][cur]=%ld\n", N, i, par, cur, dp3[par][cur]);
  //  dfs3(cur, par);
  }
  for (auto cur: edge[par]) {
    if (cur == ppar) continue;
    dfs3(cur, par);
  }
}

int main() {
  cin >> N >> M;
  for (int i=0; i<N-1; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    edge[x].push_back(y);
    edge[y].push_back(x);
  }
  dfs(0, -1);
  dfs3(0, -1);
  dfs2(0, -1);
  for (int i=0; i<N; i++) {
    cout << dp2[i] << endl;
  }
  return 0;
}

提出情報

ジャッジ結果