結果

問題 No.1424 Ultrapalindrome
ユーザー zkou
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

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