結果

問題 No.399 動的な領主
ユーザー norioc
提出日時 2025-03-12 01:59:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 788 ms / 2,000 ms
コード長 2,405 bytes
コンパイル時間 441 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 190,216 KB
最終ジャッジ日時 2025-03-12 01:59:30
合計ジャッジ時間 9,562 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)


class LCA:
    def __init__(self, n, adj, root=0):
        K = 1
        while (1 << K) < n: K += 1
        parent = [[-1] * n for _ in range(K)]
        dist = [-1] * n

        def dfs():
            s = [(root, -1, 0)]
            while s:
                v, par, depth = s.pop()
                parent[0][v] = par
                dist[v] = depth
                for to in adj[v]:
                    if to == par: continue
                    s.append((to, v, depth+1))

        dfs()
        for k in range(K-1):
            for v in range(n):
                if parent[k][v] < 0: continue
                parent[k+1][v] = parent[k][parent[k][v]]
        self.parent = parent
        self.dist = dist

    def query(self, u, v) -> int:
        """二頂点 u, v の LCA"""
        if self.dist[u] < self.dist[v]: u, v = v, u
        K = len(self.parent)
        # LCA までの距離を同じにする
        for k in range(K):
            if (self.dist[u] - self.dist[v]) >> k & 1:
                u = self.parent[k][u]
        # 二分探索で LCA を求める
        if u == v: return u
        for k in range(K-1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

    def distance(self, u, v) -> int:
        """二頂点 u, v の距離"""
        return self.dist[u] + self.dist[v] - 2 * self.dist[self.query(u, v)]

    def is_on_path(self, u, v, a) -> bool:
        """二頂点 u, v 上に a があるか"""
        return self.distance(u, a) + self.distance(a, v) == self.distance(u, v)


N = int(input())
adj = defaultdict(list)
for _ in range(N-1):
    u, v = map(lambda x: int(x)-1, input().split())
    adj[u].append(v)
    adj[v].append(u)

lca = LCA(N, adj, root=0)
Q = int(input())
acc = [0] * N
for _ in range(Q):
    A, B = map(lambda x: int(x)-1, input().split())
    p = lca.query(A, B)
    pp = lca.parent[0][p]
    acc[A] += 1
    acc[B] += 1
    acc[p] -= 1
    if pp != -1:
        acc[pp] -= 1


def dfs(v, par, acc):
    for to in adj[v]:
        if to == par: continue
        dfs(to, v, acc)
        acc[v] += acc[to]  # 葉から根へ累積和を計算していく


dfs(0, -1, acc)
ans = 0
for i in range(N):
    x = acc[i]
    ans += x * (x+1) // 2

print(ans)
0