結果

問題 No.1424 Ultrapalindrome
ユーザー zkouzkou
提出日時 2021-03-13 12:15:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,060 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 97,664 KB
最終ジャッジ日時 2024-10-15 04:52:23
合計ジャッジ時間 6,173 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
59,264 KB
testcase_01 AC 44 ms
53,760 KB
testcase_02 AC 45 ms
54,016 KB
testcase_03 AC 45 ms
53,632 KB
testcase_04 AC 46 ms
53,888 KB
testcase_05 AC 46 ms
53,888 KB
testcase_06 AC 45 ms
54,016 KB
testcase_07 AC 45 ms
54,016 KB
testcase_08 AC 46 ms
53,888 KB
testcase_09 AC 231 ms
97,536 KB
testcase_10 AC 208 ms
97,664 KB
testcase_11 AC 182 ms
91,136 KB
testcase_12 AC 200 ms
96,640 KB
testcase_13 AC 122 ms
80,640 KB
testcase_14 AC 202 ms
93,312 KB
testcase_15 AC 51 ms
60,416 KB
testcase_16 AC 165 ms
88,448 KB
testcase_17 AC 183 ms
91,904 KB
testcase_18 TLE -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

class LCA:
    "0-indexed"

    __slots__ = ["depth", "ancestor"]

    def __init__(self, adj):  
        N = len(adj) 
        parent = [-1] * N
        self.depth = [0] * N
        q = deque([0])
        while q:
            node = q.popleft()
            for next_node in adj[node]:
                if parent[node] != next_node:
                    parent[next_node] = node
                    q.append(next_node)
                    self.depth[next_node] = self.depth[node] + 1
                        
        self.ancestor = [parent] #self.ancestor[k][u]はuの2**k先の祖先。
        k = 1
        while (1 << k) < N:
            anc_k = [0] * N
            for u in range(N):
                if self.ancestor[-1][u] == -1:
                    anc_k[u] = -1
                else:
                    anc_k[u] = self.ancestor[-1][self.ancestor[-1][u]]
            self.ancestor.append(anc_k)
            k += 1

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        for k, bit in enumerate(reversed(format(self.depth[u]-self.depth[v], 'b'))):
            if bit == '1':
                u = self.ancestor[k][u]
        if u == v:
            return u
        for anc in reversed(self.ancestor):
            if anc[u] != anc[v]:
                u = anc[u]
                v = anc[v]
        return self.ancestor[0][u]

    def dist(self, u, v):
        w = self.lca(u, v)
        return self.depth[u] + self.depth[v] - 2 * self.depth[w]


def main():
    N = int(input())
    adj = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        adj[u].append(v)
        adj[v].append(u)

    lca = LCA(adj)
    
    leaves = [v for v in range(N) if len(adj[v]) == 1]

    dist = lca.dist(leaves[0], leaves[1])
    for i in range(len(leaves)):
        for j in range(i + 1, len(leaves)):
            if dist != lca.dist(leaves[i], leaves[j]):
                print("No")
                exit()
    print("Yes")

main()
0