Problem:


Score : 100 points

Problem Statement

There is a tree with N vertices, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N - 1), the i-th edge connects Vertex x_i and y_i.

Taro has decided to paint each vertex in white or black, so that any black vertex can be reached from any other black vertex by passing through only black vertices.

You are given a positive integer M.
For each v (1 \leq v \leq N), answer the following question:

Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

2 \leq M \leq 10^9

1 \leq x_i, y_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}

Output

Print N lines.
The v-th (1 \leq v \leq N) line should contain the answer to the following question:

Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Sample Input 1

3 100
1 2
2 3

Sample Output 1

3
4
3

There are seven ways to paint the vertices, as shown in the figure below.
Among them, there are three ways such that Vertex 1 is black, four ways such that Vertex 2 is black and three ways such that Vertex 3 is black.

Sample Input 2

4 100
1 2
1 3
1 4

Sample Output 2

8
5
5
5

Sample Input 3

1 100

Sample Output 3

1

Sample Input 4

10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7

Sample Output 4

0
0
1
1
1
0
1
0
1
1

Be sure to print the answers modulo M.



Sample input:
3 100
1 2
2 3


Sample output:
3
4
3

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=[set()for i in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    s[x-1].add(y-1)
    s[y-1].add(x-1)
if n==1:
   print(1)
   exit()
l=[None]*n
r=[None]*n
def dfs(a=0,b=None):
    s[a].discard(b)
    l[a]=[1]*(len(s[a])+1)
    r[a]=[1]*(len(s[a])+1)
    g=[dfs(i,a)+1for i in s[a]]
    for i,x in enumerate(g,1):
        l[a][i]=l[a][i-1]*x%m
    for i,x in enumerate(g,1):
        r[a][-i-1]=r[a][-i-1]*x%m
    return l[a][-1]
dfs()
dp=[None]*n
q=[(0,1)]
while q:
    x,y=q.pop()
    dp[x]=y*l[x][-1]
    for i,j,h in zip(s[x],l[x][:-1],r[x][1:]):
        q.append((i,y*j*h%m+1))
for i in dp:
    print(i)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=[set()for i in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    s[x-1].add(y-1)
    s[y-1].add(x-1)
l=[None]*n
r=[None]*n
def dfs(a=0,b=None):
    s[a].discard(b)
    l[a]=[1]*(len(s[a])+1)
    r[a]=[1]*(len(s[a])+1)
    g=[dfs(i,a)+1for i in s[a]]
    for i,x in enumerate(g,1):
        l[a][i]=l[a][i-1]*x%m
    for i,x in enumerate(g,1):
        r[a][-i-1]=r[a][-i-1]*x%m
    return l[a][-1]
dfs()
dp=[None]*n
q=[(0,1)]
while q:
    x,y=q.pop()
    dp[x]=y*l[x][-1]
    for i,j,h in zip(s[x],l[x][:-1],r[x][1:]):
        q.append((i,y*j*h%m+1))
for i in dp:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

n,m = map(int,input().split())

neighbor = {}
for i in range(1,n+1):
    neighbor[i] = []

for i in range(n-1):
    x,y = map(int, input().split())
    neighbor[x].append(y)
    neighbor[y].append(x)

dp = [{} for _ in range(n+1)]
dp_prod = [{'list':{}} for _ in range(n+1)]
prod_make_check = [0] * (n+1)
for i in range(1,n+1):
    prod_make_check[i] = -1 * len(neighbor[i])
    for idx, j in enumerate(neighbor[i]):
        dp_prod[i]['list'][j] = idx
        dp[i][j] = -1

def calc(x,y):
    if(dp[x][y] != -1):
        return(dp[x][y])

    if(len(neighbor[y]) == 1):
        dp[x][y] = 2 % m
        prod_make_check[x] += 1
        if(prod_make_check[x] == 0):
            calc_prod(x)
        return(dp[x][y])

    if(prod_make_check[y] == 0):
        idx = dp_prod[y]['list'][x]
        dp[x][y] = (1 + dp_prod[y]['left'][idx] * dp_prod[y]['right'][idx+1])  % m
        prod_make_check[x] += 1
        if(prod_make_check[x] == 0):
            calc_prod(x)
        return(dp[x][y])

    temp = 1
    for i in neighbor[y]:
        if(i == x):
            continue
        temp = temp * calc(y, i) % m
    temp = (temp+1) % m
    dp[x][y] = temp
    prod_make_check[x] += 1
    if(prod_make_check[x] == 0):
        calc_prod(x)
    return(dp[x][y])


def calc_prod(y):
    left = 1
    right = 1
    len_ = len(neighbor[y]) + 1
    dp_prod[y]['left'] = [1] * len_
    dp_prod[y]['right'] = [1] * len_
    for idx, z in enumerate(neighbor[y]):
        left = left * dp[y][z] % m
        dp_prod[y]['left'][idx+1] = left

    for idx, z in enumerate(neighbor[y][::-1]):
        right = right * dp[y][z] % m
        dp_prod[y]['right'][len_ - 2 -idx] = right

for i in range(1,n+1):
    for j in neighbor[i]:
        calc(i,j)

for i in range(1,n+1):
    print(dp_prod[i]['right'][0])

Submission status: Runtime Error

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

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
ostream &operator<<(ostream &os, pair<ll, ll>&p){
  return os << p.first << " " << p.second;
}  
template< typename sum_t, typename key_t >
struct ReRooting {
  struct Edge {
    int to;
    key_t data;
    sum_t dp, ndp;
  };

  using F = function< sum_t(sum_t, sum_t) >;
  using G = function< sum_t(sum_t, key_t) >;

  vector< vector< Edge > > g;
  vector< sum_t > subdp, dp;
  const sum_t ident;
  const F f;
  const G gg;

  ReRooting(int V, const F f, const G g, const sum_t &ident)
      : g(V), f(f), gg(g), ident(ident), subdp(V, ident), dp(V, ident) {}

  void add_edge(int u, int v, const key_t &d) {
    g[u].emplace_back((Edge) {v, d, ident, ident});
    g[v].emplace_back((Edge) {u, d, ident, ident});
  }

  void add_edge_bi(int u, int v, const key_t &d, const key_t &e) {
    g[u].emplace_back((Edge) {v, d, ident, ident});
    g[v].emplace_back((Edge) {u, e, ident, ident});
  }

  void dfs_sub(int idx, int par) {
    for(auto &e : g[idx]) {
      if(e.to == par) continue;
      dfs_sub(e.to, idx);
      subdp[idx] = f(subdp[idx], gg(subdp[e.to], e.data));
    }
  }

  void dfs_all(int idx, int par, const sum_t &top) {
    sum_t buff{ident};
    for(int i = 0; i < (int) g[idx].size(); i++) {
      auto &e = g[idx][i];
      e.ndp = buff;
      e.dp = gg(par == e.to ? top : subdp[e.to], e.data);
      buff = f(buff, e.dp);
    }
    dp[idx] = buff;
    buff = ident;
    for(int i = (int) g[idx].size() - 1; i >= 0; i--) {
      auto &e = g[idx][i];
      if(e.to != par) dfs_all(e.to, idx, f(e.ndp, buff));
      e.ndp = f(e.ndp, buff);
      buff = f(buff, e.dp);
    }
  }

  vector< sum_t > build() {
    dfs_sub(0, -1);
    dfs_all(0, -1, ident);
    return dp;
  }
};
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll n,m;cin>>n>>m;
  auto f1=[&](ll x,ll y){
    return x*y%m;
  };
  auto f2=[&](ll x,ll w){
    return x+w;
  };
  ReRooting<ll,ll> rr(n,f1,f2,1);
  rep(i,0,n-1){
    int u,v;cin>>u>>v;u--;v--;
    rr.add_edge(u,v,1);
  }
  auto ret=rr.build();
  rep(i,0,n)cout<<ret[i]<<endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import defaultdict
from collections import deque


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))


def array(*args, initial=0):
    Spre, Spost = "", ""
    while len(args) > 0:
        Spre += "["
        Spost += " for _ in range("+str(args[-1])+")]"
        args = args[:-1]
    S = Spre + str(initial) + Spost
    return eval(S)


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    g = Graph(N)
    for xx, yy in zip(x, y):
        g.add_edge(xx-1, yy-1)
        g.add_edge(yy-1, xx-1)

    dp = [0]*N

    def dfs(node, par=-1):
        dp[node] = 1
        for child, _ in g.E[node]:
            if child == par:
                continue
            dfs(child, node)
            dp[node] *= dp[child] + 1

    ans = [0]*N

    def dfs_2(node, par=-1):
        ans[node] = 1
        for child, _ in g.E[node]:
            ans[node] *= dp[child]+1

        # 一要素を覗いた積を求めるため、昇順の積、降順の積を求めておく
        M = len(g.E[node])
        left, right = [1]*M, [1]*M
        for i in range(M):
            t, w = g.E[node][i]
            left[i] = left[i-1]*(dp[t]+1)
            t, w = g.E[node][M-i-1]
            right[i] = right[M-i-1]*(dp[t]+1)

        for i in range(M):
            child, _ = g.E[node][i]
            if child == par:
                continue
            dp[node] = 1
            if i:
                dp[node] *= left[i-1]
            if i+1 < M:
                dp[node] *= right[i+1]
            dfs_2(child, node)
    dfs(0)
    dfs_2(0)

    print(*ans, sep="\n")

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (N - 1)  # type: "List[int]"
    y = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
gra = dd(list)
n,m = map(int, input().split())
for i in range(n-1):
    u,v = map(int, input().split())
    gra[u].append(v)
    gra[v].append(u)
dp = {} # (tar, par)
def visit_1(x,p=None):
    res = 1
    for w in gra[x]:
        if w != p:
            visit_1(w,x)
            res = (res * (1 + dp[(w,x)])) % m
    dp[(x,p)] = res
def visit_2(x,p=None):
    wn = len(gra[x])
    lp = [1 + dp[(w,x)] for w in gra[x]]
    rp = lp[:]
    for i in range(1,wn):
        lp[i] = (lp[i] * lp[i-1]) % m
        rp[wn-1-i] = (rp[wn-1-i] * rp[wn-i]) % m
    for i,w in enumerate(gra[x]):
        if w != p:
            res = 1
            if i > 0:
                res = (res * lp[i-1]) % m
            if i < wn - 1:
                res = (res * rp[i+1]) % m
            dp[(x,w)] = res
            visit_2(w,x)
def ans(x):
    res = 1
    for w in gra[x]:
        res = (res * (1 + dp[(w,x)])) % m
    return res
visit_1(1)
visit_2(1)
for x in range(1,n+1):
    print(ans(x))

Submission status: Runtime Error

Solution code:
from collections import deque
import copy
def makeTree(i):
    if len(G[i])==1 and G[i][0]==T[i][0]:
        return
    for j in G[i]:
        if j!=T[i][0]:
            T[i].append(j)
            T[j] = [i]
            makeTree(j)
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
# Tree
T = {1:[0]}
makeTree(1)
# dp
T1 = copy.deepcopy(T)
dp = [[1 for _ in range(N+1)] for _ in range(N+1)]
C = []
stack = deque([1])
while stack:
    cur = stack[-1]
    if len(T1[cur])==1:
        C.append(stack.pop())
        if cur!=1:
            T1[T1[cur][0]].remove(cur)
    else:
        for x in T1[cur][1:]:
            stack.append(x)
for i in range(N):
    cur = C[i]
    if len(T[cur])==1:
        dp[cur][T[cur][0]] = 1
    else:
        for x in T[cur][1:]:
            dp[cur][T[cur][0]] = (dp[cur][T[cur][0]]*(dp[x][cur]+1))%M
stack = deque([1])
Cr = []
while stack:
    cur = stack.pop()
    Cr.append(cur)
    for x in T[cur][1:]:
        stack.append(x)
for i in range(N):
    cur = Cr[i]
    if cur==1:
        tot = 1
    else:
        tot = dp[T[cur][0]][cur]+1
    for x in T[cur][1:]:
        tot *= (dp[x][cur]+1)
    for x in T[cur][1:]:
        dp[cur][x] = (tot//(dp[x][cur]+1))%M
for i in range(1,N+1):
    cnt = 1
    for x in G[i]:
        cnt = (cnt*(dp[x][i]+1))%M
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

N,MOD = map(int,readline().split())
m = map(int,read().split())
XY = zip(m,m)

mult = lambda x,y: x*y%MOD

graph = [[] for _ in range(N+1)]
for x,y in XY:
    graph[x].append(y)
    graph[y].append(x)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

# 自身を黒く塗ったときの根側
dp1 = [0]*(N+1)

for v in order[::-1]:
    x = 1
    for w in graph[v]:
        x *= dp1[w]+1
        x %= MOD
    dp1[v] = x

# 親側
dp2 = [1]*(N+1)

for v in order:
    p = parent[v]
    arr = [dp1[c]+1 if c != p else dp2[v] for c in graph[v]]
    # 1元を除く積を取得
    from_left = [1] + list(itertools.accumulate(arr,mult))[:-1]
    from_right = list(itertools.accumulate(reversed(arr),mult))[-2::-1] + [1]
    prod = [x*y%MOD for x,y in zip(from_left,from_right)]
    for c,x in zip(graph[v],prod):
        if c != p:
            dp2[c] = 1+x

answer = '\n'.join(str(x*y%MOD) for x,y in zip(dp1[1:],dp2[1:]))
print(answer)

Submission status: Runtime Error

Solution code:
#全方位木DPによって求める
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9 + 7)


def get_par_tree(tree: list, par: int) -> list:
    """親を求める"""
    n = len(tree)
    ans = [-1] * n
    visited = [False] * n
    visited[par] = True
    q = deque([par])
    while q:
        pos = q.popleft()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            ans[next_pos] = pos
    return ans


def topological_sort(graph: list) -> list:
    """入力した重みなしDAGに対してトポロジカルソートする
    計算量: O(|V|+|E|)
    入力条件: グラフGはDAGである、グラフGに多重辺はない、グラフGに自己ループはない
    """
    n = len(graph)
    degree = [0] * n
    for g in graph:
        for next_pos in g:
            degree[next_pos] += 1

    # 次数が0、つまり入力の無い頂点を初期値状態とする
    ans = [i for i in range(n) if degree[i] == 0]

    q = deque(ans)
    while q:
        pos = q.popleft()
        for next_pos in graph[pos]:
            degree[next_pos] -= 1
            if degree[next_pos] == 0:
                q.append(next_pos)
                ans.append(next_pos)
    return ans


def dfs1():
    """その頂点の部分木での黒色で塗るパターンを求める"""
    visited = [False] * n
    for pos in tp_list:
        visited[pos] = True
        for next_pos in graph[pos]:
            if visited[next_pos]:
                continue
            b1[next_pos] *= (1 + b1[pos])
            b1[next_pos] %= MOD


def dfs2():
    """全方位木DP"""
    for pos in tp_list:
        cnt = 0
        b = 1
        par = par_list[pos]
        for next_pos in graph[pos]:
            if next_pos == par:
                d = child_pos[par][pos]
                tmp_b = ruiseki_child_l[par][d] * ruiseki_child_r[par][-d-2]
                tmp_b %= MOD
                b *= (1 + tmp_b)
                b %= MOD
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + tmp_b)
                cnt += 1
            else:
                b *= (1 + b1[next_pos])
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + b1[next_pos])
                cnt += 1
                b %= MOD
        b2[pos] = b
        ruiseki_child_l[pos] += child_val[pos] 
        ruiseki_child_r[pos] += child_val[pos][::-1]
        for i in range(len(child_val[pos])):
            ruiseki_child_r[pos][i+1] = ruiseki_child_r[pos][i] * ruiseki_child_r[pos][i+1]
            ruiseki_child_l[pos][i+1] = ruiseki_child_l[pos][i] * ruiseki_child_l[pos][i+1]
            ruiseki_child_r[pos][i+1] %= MOD
            ruiseki_child_l[pos][i+1] %= MOD


n, m = map(int, input().split())
MOD = m
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]
dag = [[] for i in range(n)]

for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[b].append(a)
    graph[a].append(b)
    dag[b].append(a)

par_list = get_par_tree(graph, 0)
tp_list = topological_sort(dag)
b1 = [1] * n
dfs1()

child_pos = defaultdict(lambda :defaultdict(dict))
child_val = [[] for i in range(n)]
ruiseki_child_l = [[1] for i in range(n)]
ruiseki_child_r = [[1] for i in range(n)]
tp_list = tp_list[::-1]
b2 = [0] * n
dfs2()

for num in b2:
    print(num % MOD)

Submission status: Runtime Error

Solution code:
#全方位木DPによって求める
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9 + 7)


def get_par_tree(tree: list, par: int) -> list:
    """親を求める"""
    n = len(tree)
    ans = [-1] * n
    visited = [False] * n
    visited[par] = True
    q = deque([par])
    while q:
        pos = q.popleft()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            ans[next_pos] = pos
    return ans


def topological_sort(graph: list) -> list:
    """入力した重みなしDAGに対してトポロジカルソートする
    計算量: O(|V|+|E|)
    入力条件: グラフGはDAGである、グラフGに多重辺はない、グラフGに自己ループはない
    """
    n = len(graph)
    degree = [0] * n
    for g in graph:
        for next_pos in g:
            degree[next_pos] += 1

    # 次数が0、つまり入力の無い頂点を初期値状態とする
    ans = [i for i in range(n) if degree[i] == 0]

    q = deque(ans)
    while q:
        pos = q.popleft()
        for next_pos in graph[pos]:
            degree[next_pos] -= 1
            if degree[next_pos] == 0:
                q.append(next_pos)
                ans.append(next_pos)
    return ans


def dfs1():
    """その頂点の部分木での黒色で塗るパターンを求める"""
    visited = [False] * n
    for pos in tp_list:
        visited[pos] = True
        for next_pos in graph[pos]:
            if visited[next_pos]:
                continue
            b1[next_pos] *= (1 + b1[pos])
            b1[next_pos] %= MOD


def dfs2():
    """全方位木DP"""
    for pos in tp_list:
        cnt = 0
        b = 1
        par = par_list[pos]
        for next_pos in graph[pos]:
            if next_pos == par:
                d = child_pos[par][pos]
                tmp_b = ruiseki_child_l[par][d] * ruiseki_child_r[par][-d-2]
                tmp_b %= MOD
                b *= (1 + tmp_b)
                b %= MOD
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + tmp_b)
                cnt += 1
            else:
                b *= (1 + b1[next_pos])
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + b1[next_pos])
                cnt += 1
                b %= MOD
        b2[pos] = b
        ruiseki_child_l[pos] += child_val[pos] 
        ruiseki_child_r[pos] += child_val[pos][::-1]
        for i in range(len(child_val[pos])):
            ruiseki_child_r[pos][i+1] = ruiseki_child_r[pos][i] * ruiseki_child_r[pos][i+1]
            ruiseki_child_l[pos][i+1] = ruiseki_child_l[pos][i] * ruiseki_child_l[pos][i+1]
            ruiseki_child_r[pos][i+1] %= MOD
            ruiseki_child_l[pos][i+1] %= MOD


n, m = map(int, input().split())
MOD = m
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]
dag = [[] for i in range(n)]

for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[b].append(a)
    graph[a].append(b)
    dag[b].append(a)

par_list = get_par_tree(graph, 0)
tp_list = topological_sort(dag)
b1 = [1] * n
dfs1()

child_pos = defaultdict(lambda :defaultdict(dict))
child_val = [[] for i in range(n)]
ruiseki_child_l = [[1] for i in range(n)]
ruiseki_child_r = [[1] for i in range(n)]
tp_list = tp_list[::-1]
b2 = [1] * n
dfs2()

for num in b2:
    print(num % MOD)

Submission status: Runtime Error

Solution code:
#全方位木DPによって求める
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9 + 7)


def get_par_tree(tree: list, par: int) -> list:
    """親を求める"""
    n = len(tree)
    ans = [-1] * n
    visited = [False] * n
    visited[par] = True
    q = deque([par])
    while q:
        pos = q.popleft()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            ans[next_pos] = pos
    return ans


def topological_sort(graph: list) -> list:
    """入力した重みなしDAGに対してトポロジカルソートする
    計算量: O(|V|+|E|)
    入力条件: グラフGはDAGである、グラフGに多重辺はない、グラフGに自己ループはない
    """
    n = len(graph)
    degree = [0] * n
    for g in graph:
        for next_pos in g:
            degree[next_pos] += 1

    # 次数が0、つまり入力の無い頂点を初期値状態とする
    ans = [i for i in range(n) if degree[i] == 0]

    q = deque(ans)
    while q:
        pos = q.popleft()
        for next_pos in graph[pos]:
            degree[next_pos] -= 1
            if degree[next_pos] == 0:
                q.append(next_pos)
                ans.append(next_pos)
    return ans


def dfs1():
    """その頂点の部分木での黒色で塗るパターンを求める"""
    visited = [False] * n
    for pos in tp_list:
        visited[pos] = True
        for next_pos in graph[pos]:
            if visited[next_pos]:
                continue
            b1[next_pos] *= (1 + b1[pos])
        b1[next_pos] %= MOD


def dfs2():
    """全方位木DP"""
    for pos in tp_list:
        cnt = 0
        b = 1
        par = par_list[pos]
        for next_pos in graph[pos]:
            if next_pos == par:
                d = child_pos[par][pos]
                tmp_b = ruiseki_child_l[par][d] * ruiseki_child_r[par][-d-2]
                tmp_b %= MOD
                b *= (1 + tmp_b)
                b %= MOD
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + tmp_b)
                cnt += 1
            else:
                b *= (1 + b1[next_pos])
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + b1[next_pos])
                cnt += 1
                b %= MOD
        b2[pos] = b
        ruiseki_child_l[pos] += child_val[pos] 
        ruiseki_child_r[pos] += child_val[pos][::-1]
        for i in range(len(child_val[pos])):
            ruiseki_child_r[pos][i+1] = ruiseki_child_r[pos][i] * ruiseki_child_r[pos][i+1]
            ruiseki_child_l[pos][i+1] = ruiseki_child_l[pos][i] * ruiseki_child_l[pos][i+1]
            ruiseki_child_r[pos][i+1] %= MOD
            ruiseki_child_l[pos][i+1] %= MOD


n, m = map(int, input().split())
MOD = m
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]
dag = [[] for i in range(n)]

for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[b].append(a)
    graph[a].append(b)
    dag[b].append(a)

par_list = get_par_tree(graph, 0)
tp_list = topological_sort(dag)
b1 = [1] * n
dfs1()

child_pos = defaultdict(lambda :defaultdict(dict))
child_val = [[] for i in range(n)]
ruiseki_child_l = [[1] for i in range(n)]
ruiseki_child_r = [[1] for i in range(n)]
tp_list = tp_list[::-1]
b2 = [1] * n
dfs2()

for num in b2:
    print(num % MOD)

Submission status: Runtime Error

Solution code:
#全方位木DPによって求める
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9 + 7)


def dfs1(pos, par):
    """その頂点の部分木での黒色で塗るパターンを求める"""
    b = 1
    for next_pos in graph[pos]:
        if next_pos == par:
            continue
        tmp_b = dfs1(next_pos, pos)
        b *= (1 + tmp_b)
        b %= MOD
    b1[pos] = b
    return b


def dfs2(pos, par):
    """全方位木DP"""
    b = 1
    cnt = 0
    tmp = [1]
    for next_pos in graph[pos]:
        if next_pos == par:
            d = child_pos[par][pos]
            tmp_b = ruiseki_child_l[par][d] * ruiseki_child_r[par][-d-2]
            tmp_b %= MOD
            b *= (1 + tmp_b)
            b %= MOD
            child_pos[pos][next_pos] = cnt
            tmp.append(1 + tmp_b)
            cnt += 1
        else:
            b *= (1 + b1[next_pos])
            child_pos[pos][next_pos] = cnt
            tmp.append(1 + b1[next_pos])
            cnt += 1
            b %= MOD
    b2[pos] = b
    ruiseki_child_l[pos] += tmp 
    ruiseki_child_r[pos] += tmp[::-1]
    for i in range(len(child_val[pos])):
        ruiseki_child_r[pos][i+1] = ruiseki_child_r[pos][i] * ruiseki_child_r[pos][i+1]
        ruiseki_child_l[pos][i+1] = ruiseki_child_l[pos][i] * ruiseki_child_l[pos][i+1]
        ruiseki_child_r[pos][i+1] %= MOD
        ruiseki_child_l[pos][i+1] %= MOD
    for next_pos in graph[pos]:
        if next_pos != par:
            dfs2(next_pos, pos)


                
n, m = map(int, input().split())
MOD = m
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]
for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

child_pos = defaultdict(lambda :defaultdict(dict))

b1 = [0] * n
dfs1(0, -1)

ruiseki_child_l = [[1] for i in range(n)]
ruiseki_child_r = [[1] for i in range(n)]
b2 = [0] * n
dfs2(0, -1)

for i in range(n):
    print(b2[i] % MOD)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)


n, m = list(map(int, input().split()))
dp = [-1]*n

xx = {}

g = [set() for i in range(n)]

for i in range(n-1):
    x, y = list(map(int, input().split()))
    x-=1
    y-=1
    g[x].add(y)
    g[y].add(x)

# sys.exit(0)

def solve(u, p):

    if (dp[u]!=-1):
        return dp[u]

    ans = 1
    for v in g[u]:
        if v==p:
            continue
        
        ans *= (1+solve(v, u))
    dp[u]=ans
    return ans
    

def solve2(u, p):
    #u is at the root
    xx[u]=dp[u]

    for v in g[u]:
        if v==p:
            continue
        dp[u]/=(1+dp[v])
        dp[v]*=(1+dp[u])
        solve2(v, u)
        dp[v]/=(1+dp[u])
        dp[u]*=(1+dp[v])
        
solve(0,-1)
solve2(0, -1)

for i in range(n):
    print(int(xx[i]%m))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, MOD = [int(i) for i in input().split()]
adj = [[] for _ in [0] * (n+1)]
dp = [[0, 0] for i in range(n+1)]
dp2 = [0] * (n+1)


def dfs1(node, pn):
    dp[node] = [1, 1]
    for i in adj[node]:
        if i == pn:
            continue
        dfs1(i, node)
        dp[node][0] = (dp[node][0] * (dp[i][0] + dp[i][1]))
        dp[node][1] = (dp[node][1] * dp[i][1])
    return



def dfs2(node, pn):
    dp2[node] = dp[node][0] % MOD

    for i in adj[node]:
        if i == pn:
            continue

        dp[node][0] = (dp[node][0] / (dp[i][0] + dp[i][1]));
        dp[node][1] = (dp[node][1] / dp[i][1]);
        dp[i][0] = (dp[i][0] * (dp[node][0] + dp[node][1]));
        dp[i][1] = (dp[i][1] * dp[node][1]);
        dfs2(i, node);
        dp[i][1] = (dp[i][1] / dp[node][1]);
        dp[i][0] = (dp[i][0] / (dp[node][0] + dp[node][1]));
        dp[node][0] = (dp[node][0] * (dp[i][0] + dp[i][1]));
        dp[node][1] = (dp[node][1] * dp[i][1]);
    return



for _ in range(n-1):
    x, y = [int(i) for i in input().split()]
    adj[x].append(y)
    adj[y].append(x)

dfs1(1, -1)
dfs2(1, -1)

for i in range(1, n+1):
    print(int(dp2[i]))

Submission status: Runtime Error

Solution code:
import itertools
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].add(y)
    graph[y].add(x)

dp_1 = [None] * (N+1)
products = [[] for _ in range(N+1)]

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    x = 1
    graph[v].discard(parent)
    if graph[v]:
        arr = [dfs_1(w,v)+1 for w in graph[v]]
        L = list(itertools.accumulate(arr[:-1], lambda x,y: x*y%MOD))
        R = list(itertools.accumulate(arr[1:][::-1], lambda x,y: x*y%MOD))[::-1]
        products[v] = [x*y%MOD for x,y in zip(L,R)]
        dp_1[v] = products[v][0] * arr[0] % MOD
    else:
        dp_1[v] = 1
    return dp_1[v]

dp_1 = [0] * (N+1) # 自分を黒く塗って、子側の部分木を適切に塗る方法
dfs_1()

Submission status: Runtime Error

Solution code:
import itertools
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].add(y)
    graph[y].add(x)

dp_1 = [None] * (N+1)
products = [[] for _ in range(N+1)]

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    x = 1
    graph[v].discard(parent)
    if graph[v]:
        arr = [dfs_1(w,v)+1 for w in graph[v]]
        L = [1] + list(itertools.accumulate(arr[:-1], lambda x,y: x*y%MOD))
        R = list(itertools.accumulate(arr[1:][::-1], lambda x,y: x*y%MOD))[::-1] + [1]
        products[v] = [x*y%MOD for x,y in zip(L,R)]
        dp_1[v] = products[v][0] * arr[0] % MOD
    else:
        dp_1[v] = 1
    return dp_1[v]

dp_1 = [0] * (N+1) # 自分を黒く塗って、子側の部分木を適切に塗る方法
dfs_1()

dp_1

products

def dfs_2(v=1,x=1):
    # それぞれの子以外の情報をマージして、子に渡さなければいけない
    dp[v] = x * dp_1[v] % MOD
    for w,p in zip(graph[v],products[v]):
        dfs_2(w,x*p%MOD+1)

dp = [None] * (N+1)
dfs_2()

print('\n'.join(map(str,dp[1:])))