Submission #11958953


Source Code Expand

Copy
#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;
}

Submission Info

Submission Time
Task V - Subtree
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2252 Byte
Status
Exec Time 430 ms
Memory 40064 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
× 36
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24, 1_25, 1_26, 1_27, 1_28, 1_29, 1_30, 1_31
Case Name Status Exec Time Memory
0_00 4 ms 9088 KB
0_01 4 ms 9088 KB
0_02 3 ms 9088 KB
0_03 3 ms 9216 KB
1_00 3 ms 9088 KB
1_01 3 ms 9088 KB
1_02 373 ms 38912 KB
1_03 416 ms 38144 KB
1_04 301 ms 20344 KB
1_05 299 ms 21112 KB
1_06 321 ms 20216 KB
1_07 327 ms 20984 KB
1_08 295 ms 19456 KB
1_09 302 ms 20352 KB
1_10 290 ms 19328 KB
1_11 285 ms 20096 KB
1_12 282 ms 19584 KB
1_13 286 ms 20352 KB
1_14 319 ms 20736 KB
1_15 304 ms 21504 KB
1_16 314 ms 22400 KB
1_17 339 ms 23424 KB
1_18 336 ms 23424 KB
1_19 333 ms 24192 KB
1_20 327 ms 23808 KB
1_21 334 ms 24832 KB
1_22 334 ms 24448 KB
1_23 334 ms 25216 KB
1_24 331 ms 24448 KB
1_25 385 ms 25472 KB
1_26 338 ms 25472 KB
1_27 346 ms 25600 KB
1_28 392 ms 29696 KB
1_29 349 ms 28672 KB
1_30 362 ms 34560 KB
1_31 430 ms 40064 KB