Problem p02728 (python)

Fixed submission:
def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 200000):
        fact.append(fact[-1]*i % mod)
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    g2 = [set(i) for i in g]
    child = [1]*n  # 子の数
    q = [-1, 0]
    while len(q) > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            g2[j].remove(i)
            q.append(j)
        else:
            q.pop()
            if len(q) > 1:
                child[q[-1]] += child[i]
    rank = [(j, i) for i, j in enumerate(child)]
    rank = [j for i, j in sorted(rank)]
    dp = [1]*n
    for i in rank:
        c = child[i]
        ans = fact[c-1]
        temp = 1
        for j in g[i]:
            if child[j] < c:
                ans = ans*dp[j] % mod
                temp = temp*fact[child[j]] % mod
        dp[i] = ans*pow(temp, mod-2, mod) % mod
    dp2 = [0]*n
    dp2[0] = dp[0]
    g2 = [set(i) for i in g]
    q = [-1, 0]
    while len(q) > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            c = child[j]
            temp = fact[n-c]*fact[c-1]
            dp2[j] = dp2[i]*(fact[c]*fact[n-c-1])*pow(temp, mod-2, mod) % mod
            g2[j].remove(i)
            q.append(j)
        else:
            q.pop()
            if len(q) > 1:
                child[q[-1]] += child[i]

    for i in dp2:
        print(i)


main()

Buggy submission (verdict: Runtime Error):
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    mod = 10**9+7

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**5):
        fact.append(fact[-1]*i % mod)

    def inv_n(n):
        return pow(n, mod-2, mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod

    class rerooting():
        # addは頂点iに頂点jを根とする部分木（DPの値：x）をくっつけるときの補正
        def __init__(self, tree, ini):
            # merge:頂点aにbをマージするときのモノイド
            # adj_bu:ボトムアップ時の調整（a:値,i:頂点）
            # adj_td:トップダウン時の調整（a:値,i:頂点,p:親）
            # adj_fin:最終調整（a:値,i:頂点）
            def merge(a, b): return a * b % mod
            def adj_bu(a, i): return a * inv_n(size[i]) % mod
            def adj_td(a, i, p): return a * inv_n(n-size[i]) % mod
            def adj_fin(a, i): return a * fact[n-1] % mod

            # トポロジカルソートをする
            # T:木の隣接グラフ表現をset化
            # P:親
            # q:キュー
            # order:トポソしたもの
            T = [set(i) for i in tree]
            P = [-1]*n
            q = [0]
            order = []
            while q:
                i = q.pop()
                order.append(i)
                for a in T[i]:
                    if a != P[i]:
                        P[a] = i
                        T[a].remove(i)
                        q.append(a)

            # Tをリストに変換
            T = [list(i) for i in T]

            # サイズの処理を先に行う
            # size[i]:0を根とする根付き木における、iを根とする部分木の大きさ
            size = [1]*n
            for i in order[1:][::-1]:
                size[P[i]] += size[i]

            # ボトムアップ処理をする
            # ME:マージした値を一時保存
            # DP:DP値、MEを調整したもの
            ME = [ini]*n
            DP = [0]*n
            for i in order[1:][::-1]:
                DP[i] = adj_bu(ME[i], i)
                p = P[i]
                ME[p] = merge(ME[p], DP[i])
            DP[order[0]] = adj_fin(ME[order[0]], order[0])
            TD = [ini]*n

            # トップダウン処理をする
            for i in order:
                # 左からDP（結果はTDに入れている）
                ac = TD[i]
                for j in T[i]:
                    TD[j] = ac
                    ac = merge(ac, DP[j])
                # 右からDP（結果はacに入れている、一度しか使わないのでacで問題ない）
                ac = ini
                for j in T[i][::-1]:
                    TD[j] = adj_td(merge(TD[j], ac), j, i)
                    ac = merge(ac, DP[j])
                    DP[j] = adj_fin(merge(ME[j], TD[j]), j)
            for i in DP:
                print(i)

    rerooting(g, 1)


main()

Buggy submission (verdict: Runtime Error):
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    mod = 10**9+7

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**5):
        fact.append(fact[-1]*i % mod)

    def inv_n(n):
        return pow(n, mod-2, mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod

    class rerooting():
        # addは頂点iに頂点jを根とする部分木（DPの値：x）をくっつけるときの補正
        def __init__(self, tree, ini):
            # merge:頂点aにbをマージするときのモノイド
            # adj_bu:ボトムアップ時の調整（a:値,i:頂点）
            # adj_td:トップダウン時の調整（a:値,i:頂点,p:親）
            # adj_fin:最終調整（a:値,i:頂点）
            def merge(a, b): return a * b % mod
            def adj_bu(a, i): return a * inv_n(size[i]) % mod
            def adj_td(a, i, p): return a * inv_n(n-size[i]) % mod
            def adj_fin(a, i): return a * fact[n-1] % mod

            # トポロジカルソートをする
            # T:木の隣接グラフ表現をset化
            # P:親
            # q:キュー
            # order:トポソしたもの
            T = [set(i) for i in tree]
            P = [-1]*n
            q = [0]
            order = []
            while q:
                i = q.pop()
                order.append(i)
                for a in T[i]:
                    if a != P[i]:
                        P[a] = i
                        T[a].remove(i)
                        q.append(a)

            # Tをリストに変換
            T = [list(i) for i in T]

            # サイズの処理を先に行う
            # size[i]:0を根とする根付き木における、iを根とする部分木の大きさ
            size = [1]*n
            for i in order[1:][::-1]:
                size[P[i]] += size[i]

            # ボトムアップ処理をする
            # ME:マージした値を一時保存
            # DP:DP値、MEを調整したもの
            ME = [ini]*n
            DP = [0]*n
            for i in order[1:][::-1]:
                DP[i] = adj_bu(ME[i], i)
                p = P[i]
                ME[p] = merge(ME[p], DP[i])
            DP[order[0]] = adj_fin(ME[order[0]], order[0])
            TD = [ini]*n
            
            # トップダウン処理をする
            for i in order:
                # 左からDP（結果はTDに入れている）
                ac = TD[i]
                for j in T[i]:
                    TD[j] = ac
                    ac = merge(ac, DP[j])
                # 右からDP（結果はacに入れている、一度しか使わないのでacで問題ない）
                ac = ini
                for j in T[i][::-1]:
                    TD[j] = adj_td(merge(TD[j], ac), j, i)
                    ac = merge(ac, DP[j])
                    DP[j] = adj_fin(merge(ME[j], TD[j]), j)
            print(DP)

    rerooting(g, 1)


main()

Buggy submission (verdict: Runtime Error):
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 200001):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class rerooting():
        # addは頂点iに頂点jを根とする部分木（DPの値：x）をくっつけるときの補正
        def __init__(self, tree, ini):
            # 頂点iについて、jが根のときのDPの値を求める（アクセス時間を考慮してここで定義）
            def add(i, j, x):
                return x+1

            def monoid(i, j):
                return i+j

            def monoid2(i, j):
                return i*j % mod

            def calc(i, j):
                root = tree_d[i][j]+1
                try:
                    return monoid(tc_l[i][root-1], tc_r[i][root])
                except:
                    return tc_l[i][root-1]

            def calc2(i, j):
                root = tree_d[i][j]+1
                try:
                    return monoid2(tc_l2[i][root-1], tc_r2[i][root]) *\
                        nCr(tc_l[i][root-1]+tc_r[i][root], tc_l[i][root-1])
                except:
                    return tc_l2[i][root-1]

            size = len(tree)
            dp, dp2, order, q, anc = [ini]*size, [1]*size, [], [0], [-1]*n
            oa, qa, qp = order.append, q.append, q.pop
            tree_d = [{k: j for j, k in enumerate(i)} for i in g]
            g_size = [len(i) for i in g]
            tc_l = [[ini]*(i+1) for i in g_size]
            tc_r = [[ini]*i for i in g_size]
            tc_l2 = [[1]*(i+1) for i in g_size]
            tc_r2 = [[1]*i for i in g_size]

            # トポロジカル順序をorderに記録、0を根とする根付き木上のiの祖先をanc[i]とする
            while q:
                i = qp()
                a = anc[i]
                oa(i)
                for j in g[i]:
                    if j != a:
                        qa(j)
                        anc[j] = i

            # dpおよびtree_preに記録
            for i in order[:0:-1]:
                a = anc[i]
                t = tree_d[a][i]
                d = dp2[i]
                tc_l2[a][t+1], tc_r2[a][t] = d, d
                d = add(a, i, dp[i])
                tc_l[a][t+1], tc_r[a][t], dp[a] = d, d, monoid(dp[a], d)
                dp2[a] = dp2[a]*dp2[i]*nCr(dp[a], dp[i]+1) % mod

            # 頂点0のみ先に処理
            for j in range(1, g_size[0]+1):
                tc_l[0][j] = monoid(tc_l[0][j], tc_l[0][j-1])
                tc_l2[0][j] = tc_l2[0][j]*tc_l2[0][j-1] * \
                    nCr(tc_l[0][j], tc_l[0][j-1]) % mod
            for j in range(g_size[0]-1, 0, -1):
                tc_r[0][j] = monoid(tc_r[0][j], tc_r[0][j+1])
                tc_r2[0][j] = tc_r2[0][j]*tc_r2[0][j+1] * \
                    nCr(tc_r[0][j], tc_r[0][j+1]) % mod

            # 行きがけ順に処理
            for i in order[1:]:
                a = anc[i]
                d, c, c2, length = tree_d[i][a], add(
                    a, i, calc(a, i)), calc2(a, i), g_size[i]

                tc_l[i][d+1], tc_r[i][d] = c, c
                tc_l2[i][d+1], tc_r2[i][d] = c2, c2

                for j in range(1, length+1):
                    tc_l[i][j] = monoid(tc_l[i][j], tc_l[i][j-1])
                    tc_l2[i][j] = tc_l2[i][j]*tc_l2[i][j-1] * \
                        nCr(tc_l[i][j], tc_l[i][j-1]) % mod
                for j in range(length-2, 0, -1):
                    tc_r[i][j] = monoid(tc_r[i][j+1], tc_r[i][j])
                    tc_r2[i][j] = tc_r2[i][j]*tc_r2[i][j+1] * \
                        nCr(tc_r[i][j], tc_r[i][j+1]) % mod
                dp[i] = tc_l[i][-1]
                dp2[i] = tc_l2[i][-1]

            # アトリビュートに格納
            for i in dp2:
                print(i)

    rerooting(g, 0)


main()

Buggy submission (verdict: Runtime Error):
def main():
    #import random

    # def sample_tree(n):  # n頂点の連結グラフを出力する
    #    l = [random.randrange(0, i+1) for i in range(n-1)]  # 親を指定する
    #    d = {i: j for i, j in enumerate(random.sample(range(n), n))}  # シャッフル
    #    xy = sorted([sorted([d[j]+1, d[i+1]+1])
    #                 for i, j in enumerate(l)])  # グラフを作成
    #    return xy
    #n = 200000
    # print(n)
    #ab = sample_tree(n)

    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 2*10**5+1):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class DP():
        def __init__(self, dp=1, t=0):
            self.dp = dp
            self.t = t

        def __add__(self, other):
            return DP(self.dp*other.dp*nCr(self.t+other.t, self.t) % mod, self.t+other.t)

        def addRoot(self):
            return DP(self.dp, self.t+1)

    dp = [[DP() for _ in [0]*len(g[v])] for v in range(n)]
    dpSum = [DP() for _ in [0]*n]
    ans = [0]*n

    def dfs():
        visited = [0]*n
        q = [-1, 0]
        while len(q) > 1:
            v = q[-1]
            p = q[-2]
            flag = False
            while visited[v] < len(g[v]):
                i = visited[v]
                u = g[v][i]
                visited[v] += 1
                if u == p:
                    continue
                if visited[u]:
                    continue
                q.append(u)
                flag = True
                break
            if flag is False:
                i = visited[p]-1
                dp[p][i] = dpSum[v].addRoot()
                dpSum[p] = dpSum[p]+dp[p][i]
                q.pop()

    def bfs():
        q = [(0, DP(), -1)]
        while q:
            v, dpP, p = q.pop()
            deg = len(g[v])
            for i in range(deg):
                if g[v][i] == p:
                    dp[v][i] = dpP
            dpLeft = [DP() for _ in range(deg+1)]
            dpRight = [DP() for _ in range(deg+1)]
            for i in range(deg):
                dpLeft[i+1] = dpLeft[i]+dp[v][i]
            for i in range(deg-1, -1, -1):
                dpRight[i] = dpRight[i+1]+dp[v][i]
            ans[v] = dpLeft[deg].addRoot()
            for i in range(deg):
                u = g[v][i]
                if u == p:
                    continue
                d = dpLeft[i]+dpRight[i+1]
                q.append((u, d.addRoot(), v))

    dfs()
    bfs()
    for i in range(n):
        print(ans[i].dp)
    # for i in range(n):
    #    print([j.dp for j in dp[i]])


main()

Buggy submission (verdict: Runtime Error):
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**5):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class DP():
        def __init__(self, dp=1, t=0):
            self.dp = dp
            self.t = t

        def __add__(self, other):
            return DP(self.dp*other.dp*nCr(self.t+other.t, self.t) % mod, self.t+other.t)

        def addRoot(self):
            return DP(self.dp, self.t+1)

    dp = [[DP() for _ in [0]*len(g[v])] for v in range(n)]
    dpSum = [DP() for _ in [0]*n]
    ans = [0]*n

    def dfs():
        visited = [0]*n
        q = [-1, 0]
        while len(q) > 1:
            v = q[-1]
            p = q[-2]
            flag = False
            while visited[v] < len(g[v]):
                i = visited[v]
                u = g[v][i]
                visited[v] += 1
                if u == p:
                    continue
                if visited[u]:
                    continue
                q.append(u)
                flag = True
                break
            if flag is False:
                i = visited[p]-1
                dp[p][i] = dpSum[v].addRoot()
                dpSum[p] = dpSum[p]+dp[p][i]
                q.pop()

    def bfs():
        q = [(0, DP(), -1)]
        while q:
            v, dpP, p = q.pop()
            deg = len(g[v])
            for i in range(deg):
                if g[v][i] == p:
                    dp[v][i] = dpP
            dpLeft = [DP() for _ in range(deg+1)]
            dpRight = [DP() for _ in range(deg+1)]
            for i in range(deg):
                dpLeft[i+1] = dpLeft[i]+dp[v][i]
            for i in range(deg-1, -1, -1):
                dpRight[i] = dpRight[i+1]+dp[v][i]
            ans[v] = dpLeft[deg].addRoot()
            for i in range(deg):
                u = g[v][i]
                if u == p:
                    continue
                d = dpLeft[i]+dpRight[i+1]
                q.append((u, d.addRoot(), v))

    dfs()
    bfs()
    for i in range(n):
        print(ans[i].dp)
    # for i in range(n):
    #    print([j.dp for j in dp[i]])


main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    sys.setrecursionlimit(300000)
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**5):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class DP():
        def __init__(self, dp=1, t=0):
            self.dp = dp
            self.t = t

        def __add__(self, other):
            return DP(self.dp*other.dp*nCr(self.t+other.t, self.t), self.t+other.t)

        def addRoot(self):
            return DP(self.dp, self.t+1)

    dp = [[] for _ in [0]*n]
    ans = [0]*n

    def dfs(v, p=-1):
        dpSum = DP()
        dp[v] = [DP() for _ in [0]*len(g[v])]
        for i in range(len(g[v])):
            u = g[v][i]
            if u == p:
                continue
            dp[v][i] = dfs(u, v)
            dpSum = dpSum+dp[v][i]
        return dpSum.addRoot()

    def bfs(v, dpP=DP(), p=-1):
        deg = len(g[v])
        for i in range(deg):
            if g[v][i] == p:
                dp[v][i] = dpP
        dpLeft = [DP() for _ in range(deg+1)]
        dpRight = [DP() for _ in range(deg+1)]
        for i in range(deg):
            dpLeft[i+1] = dpLeft[i]+dp[v][i]
        for i in range(deg-1, -1, -1):
            dpRight[i] = dpRight[i+1]+dp[v][i]
        ans[v] = dpLeft[deg].addRoot()
        for i in range(deg):
            u = g[v][i]
            if u == p:
                continue
            d = dpLeft[i]+dpRight[i+1]
            bfs(u, d.addRoot(), v)

    dfs(0)
    bfs(0)
    for i in range(n):
        print(ans[i].dp)


main()

Buggy submission (verdict: Runtime Error):
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**5):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class DP():
        def __init__(self, dp=1, t=0):
            self.dp = dp
            self.t = t

        def __add__(self, other):
            return DP(self.dp*other.dp*nCr(self.t+other.t, self.t), self.t+other.t)

        def addRoot(self):
            return DP(self.dp, self.t+1)

    dp = [[DP() for _ in [0]*len(g[v])] for v in range(n)]
    dpSum = [DP() for _ in [0]*n]
    ans = [0]*n

    def dfs():
        visited = [0]*n
        q = [-1, 0]
        while len(q) > 1:
            v = q[-1]
            p = q[-2]
            flag = False
            while visited[v] < len(g[v]):
                i = visited[v]
                u = g[v][i]
                visited[v] += 1
                if u == p:
                    continue
                if visited[u]:
                    continue
                q.append(u)
                flag = True
                break
            if flag is False:
                i = visited[p]-1
                dp[p][i] = dpSum[v].addRoot()
                dpSum[p] = dpSum[p]+dp[p][i]
                q.pop()

    def bfs():
        q = [(0, DP(), -1)]
        while q:
            v, dpP, p = q.pop()
            deg = len(g[v])
            for i in range(deg):
                if g[v][i] == p:
                    dp[v][i] = dpP
            dpLeft = [DP() for _ in range(deg+1)]
            dpRight = [DP() for _ in range(deg+1)]
            for i in range(deg):
                dpLeft[i+1] = dpLeft[i]+dp[v][i]
            for i in range(deg-1, -1, -1):
                dpRight[i] = dpRight[i+1]+dp[v][i]
            ans[v] = dpLeft[deg].addRoot()
            for i in range(deg):
                u = g[v][i]
                if u == p:
                    continue
                d = dpLeft[i]+dpRight[i+1]
                q.append((u, d.addRoot(), v))

    dfs()
    bfs()
    for i in range(n):
        print(ans[i].dp)


main()

Buggy submission (verdict: Runtime Error):
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**5):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class DP():
        def __init__(self, dp=1, t=0):
            self.dp = dp
            self.t = t

        def __add__(self, other):
            return DP(self.dp*other.dp*nCr(self.t+other.t, self.t), self.t+other.t)

        def addRoot(self):
            return DP(self.dp, self.t+1)

    dp = [[DP() for _ in [0]*len(g[v])] for v in range(n)]
    dpSum = [DP() for _ in [0]*n]
    ans = [0]*n

    def dfs():
        visited = [0]*n
        q = [-1, 0]
        while len(q) > 1:
            v = q[-1]
            p = q[-2]
            flag = False
            while visited[v] < len(g[v]):
                i = visited[v]
                u = g[v][i]
                visited[v] += 1
                if u == p:
                    continue
                if visited[u]:
                    continue
                q.append(u)
                flag = True
                break
            if flag is False:
                i = visited[p]-1
                dp[p][i] = dpSum[v].addRoot()
                dpSum[p] = dpSum[p]+dp[p][i]
                q.pop()

    def bfs(v, dpP=DP(), p=-1):
        deg = len(g[v])
        for i in range(deg):
            if g[v][i] == p:
                dp[v][i] = dpP
        dpLeft = [DP() for _ in range(deg+1)]
        dpRight = [DP() for _ in range(deg+1)]
        for i in range(deg):
            dpLeft[i+1] = dpLeft[i]+dp[v][i]
        for i in range(deg-1, -1, -1):
            dpRight[i] = dpRight[i+1]+dp[v][i]
        ans[v] = dpLeft[deg].addRoot()
        for i in range(deg):
            u = g[v][i]
            if u == p:
                continue
            d = dpLeft[i]+dpRight[i+1]
            bfs(u, d.addRoot(), v)

    dfs()
    bfs(0)
    for i in range(n):
        print(ans[i].dp)


main()