結果

問題 No.1227 I hate ThREE
ユーザー WSKRWSKR
提出日時 2020-09-22 00:51:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 598 ms / 2,000 ms
コード長 3,462 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 87,180 KB
実行使用メモリ 125,928 KB
最終ジャッジ日時 2023-09-07 05:51:07
合計ジャッジ時間 14,040 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 97 ms
71,728 KB
testcase_01 AC 96 ms
71,904 KB
testcase_02 AC 95 ms
71,732 KB
testcase_03 AC 147 ms
79,096 KB
testcase_04 AC 148 ms
79,080 KB
testcase_05 AC 157 ms
80,816 KB
testcase_06 AC 95 ms
71,868 KB
testcase_07 AC 95 ms
71,776 KB
testcase_08 AC 181 ms
83,644 KB
testcase_09 AC 167 ms
82,392 KB
testcase_10 AC 152 ms
80,372 KB
testcase_11 AC 546 ms
121,016 KB
testcase_12 AC 598 ms
125,324 KB
testcase_13 AC 126 ms
77,536 KB
testcase_14 AC 167 ms
81,684 KB
testcase_15 AC 185 ms
84,648 KB
testcase_16 AC 286 ms
95,572 KB
testcase_17 AC 216 ms
87,704 KB
testcase_18 AC 335 ms
102,916 KB
testcase_19 AC 293 ms
97,356 KB
testcase_20 AC 365 ms
105,572 KB
testcase_21 AC 116 ms
77,568 KB
testcase_22 AC 299 ms
98,112 KB
testcase_23 AC 575 ms
124,308 KB
testcase_24 AC 598 ms
125,916 KB
testcase_25 AC 597 ms
125,928 KB
testcase_26 AC 483 ms
120,952 KB
testcase_27 AC 519 ms
123,840 KB
testcase_28 AC 531 ms
125,020 KB
testcase_29 AC 507 ms
124,908 KB
testcase_30 AC 485 ms
122,040 KB
testcase_31 AC 504 ms
122,168 KB
testcase_32 AC 534 ms
124,656 KB
testcase_33 AC 489 ms
121,732 KB
testcase_34 AC 499 ms
123,340 KB
testcase_35 AC 484 ms
121,204 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#i hate three
from collections import deque

mod = 10**9 + 7


def main():
    N, C = map(int, input().split())
    G = [[] for i in range(N+1)]
    for i in range(N-1):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)

    visited = [False for i in range(N+1)]
    depth = [0 for i in range(N+1)]
    child_cnt = [1 for i in range(N+1)]

    que = deque([])

    def dfs(s_node):
        visited[s_node] = True
        for child in G[s_node]:
            if visited[child] == False:
                depth[child] = depth[s_node] + 1
                dfs(child)
        for child in G[s_node]:
            if depth[child] > depth[s_node]:
                child_cnt[s_node] += child_cnt[child]
        que.append(s_node)

    dfs(1)

    if C > 9*N:
        dp = [[0 for i in range(6*N-5)] for i in range(N+1)]
        while que:
            node = que.popleft()
            for i in range(3*N-3):
                has_child = False
                v = 1
                for child in G[node]:
                    if depth[child] > depth[node]:
                        tmp_u = 0
                        has_child = True
                        if i >= 3:
                            tmp_u += dp[child][i-3]

                        if i+3 <= 3*N-4:
                            tmp_u += dp[child][i+3]

                        elif i+3 > 3*N-4:
                            tmp_u += pow(2, child_cnt[child]-1, mod)

                        v *= tmp_u
                        v %= mod
                dp[node][i] = v
                if has_child == False:
                    dp[node][i] = 1

            for i in range(3*N-2, 6*N-5):
                has_child = False
                v = 1
                for child in G[node]:
                    if depth[child] > depth[node]:

                        tmp_u = 0
                        has_child = True
                        if i+3 <= 6*N-6:
                            tmp_u += dp[child][i+3]
                        if i-3 >= 3*N-2:
                            tmp_u += dp[child][i-3]
                        else:
                            tmp_u += pow(2, child_cnt[child]-1, mod)

                        v *= tmp_u
                        v %= mod
                dp[node][i] = v
                if has_child == False:
                    dp[node][i] = 1

        ans = sum(dp[1][i] for i in range(3*N-3)) + sum(dp[1][i]
                                                        for i in range(3*N-2, 6*N-5)) + (C-6*N + 6)*pow(2, N-1, mod)
        print(ans % mod)
        return

    elif C <= 9*N:
        dp = [[0 for i in range(C+1)] for j in range(N+1)]
        while que:
            node = que.popleft()
            for i in range(1, C+1):
                has_child = False
                v = 1
                for child in G[node]:
                    if depth[child] > depth[node]:
                        has_child = True
                        tmp_u = 0
                        if 1 <= i-3 <= C:
                            tmp_u += dp[child][i-3]
                        if 1 <= i+3 <= C:
                            tmp_u += dp[child][i+3]
                        v *= (tmp_u)
                        v %= mod
                dp[node][i] = v % mod
                if has_child == False:
                    dp[node][i] = 1

        ans = sum(dp[1][i] for i in range(1, C+1)) % mod
        print(ans)
        return


if __name__ == "__main__":
    main()
0