結果

問題 No.399 動的な領主
ユーザー navel_tosnavel_tos
提出日時 2024-02-12 17:51:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 504 ms / 2,000 ms
コード長 3,358 bytes
コンパイル時間 548 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 114,912 KB
最終ジャッジ日時 2024-02-12 17:51:13
合計ジャッジ時間 7,367 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
53,460 KB
testcase_01 AC 35 ms
53,460 KB
testcase_02 AC 38 ms
55,604 KB
testcase_03 AC 39 ms
55,604 KB
testcase_04 AC 98 ms
76,548 KB
testcase_05 AC 186 ms
80,080 KB
testcase_06 AC 454 ms
106,192 KB
testcase_07 AC 483 ms
106,636 KB
testcase_08 AC 494 ms
106,860 KB
testcase_09 AC 487 ms
106,648 KB
testcase_10 AC 113 ms
77,340 KB
testcase_11 AC 177 ms
80,132 KB
testcase_12 AC 414 ms
109,224 KB
testcase_13 AC 426 ms
109,424 KB
testcase_14 AC 337 ms
114,912 KB
testcase_15 AC 314 ms
113,808 KB
testcase_16 AC 312 ms
109,028 KB
testcase_17 AC 504 ms
106,468 KB
testcase_18 AC 480 ms
106,432 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder 399 動的な領主

#online static LCA
class Linear_LCA:
    def __init__(self, N, G, root = 0):
        self._N = N; self._G = G; self._root = root; self._index = index = [0] * 2 * N; self._visit = visit = [-1] * N; self._depth = depth = [0] * 2 * N; self._mask = (1<<30) - 1; stack = [(root, -1, 0)]; M, logM = 2 * N, (2 * N).bit_length(); self._size = size = logM // 2; m, logm = -(-M // size), ( -(M // size) ).bit_length(); self._T = T = [[9 * 10 ** 18] * logm for _ in range(m)]; self._B = B = [0] * m; self._D = D = [None] * (1 << size - 1); has_bit = lambda S,x: S >> x & 1

        #ライブラリ改変 1/2: parentを配列定義
        self.parent = [-1] * N

        for i in range(2 * N):  #Euler Tour  index[i]: (d << 30) + v
            now, back, d = stack.pop()

            if now >= 0:
                #ライブラリ改変 2/2: parentを記録
                self.parent[now] = back

                stack.append((~now, back, d)); index[i], visit[now], depth[i] = (d << 30) + now, i, d
                for nxt in G[now]:
                    if visit[nxt] == -1: stack.append((nxt, now, d + 1))
            else: index[i], depth[i] = ((d-1) << 30) + back, d - 1
        for S in range(1 << size - 1):  #S: ibit目が1なら、depth[i] - 1 == depth[i+1]
            D[S] = dp = [[L] * size for L in range(size)]  #dp[L][R]: 最小値を満たす添字
            for Lt in range(size):
                x = y = 0
                for Rt in range(Lt + 1, size): y = y - 1 if has_bit(S, Rt - 1) else y + 1; dp[Lt][Rt] = dp[Lt][Rt - 1]; x, dp[Lt][Rt] = (y, Rt) if x > y else (x, dp[Lt][Rt])
        for b in range(m):
            Lt, Rt = size * b, min(size * (b + 1), M); T[b][0] = min(index[Lt:Rt])
            for i in range(Rt - Lt - 1): B[b] += 1 << i if depth[Lt + i] - 1 == depth[Lt + i + 1] else 0
        for j in range(logm - 1):
            mid = 1 << j
            for i in range(m): T[i][j+1] = min(T[i][j],T[i+mid][j]) if i+mid<m else T[i][j]
    def _Tmin(self, Lt, Rt): d = (Rt - Lt).bit_length() - 1; return 9 * 10 ** 18 if Lt >= Rt else min( self._T[Lt][d], self._T[Rt - (1 << d)][d] )
    def _Bmin(self, b, Lt, Rt): S, i = self._B[b], b * self._size; return self._index[ i + self._D[S][Lt][Rt] ]
    def LCA(self, u, v): ut, vt, s = self._visit[u], self._visit[v], self._size; Lt, Rt = (ut, vt) if ut <= vt else (vt, ut); Lb, Li, Rb, Ri = Lt // s, Lt % s, Rt // s, Rt % s; return self._Bmin(Lb, Li, Ri) & self._mask if Lb == Rb else min(self._Tmin(Lb + 1, Rb), self._Bmin(Lb, Li, s - 1), self._Bmin(Rb, 0, Ri)) & self._mask
        

#入力受取
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    u,v = map(int,input().split())
    G[u - 1].append(v - 1)
    G[v - 1].append(u - 1)

#LCAの前計算
LCA = Linear_LCA(N, G)

#クエリを実行  imos配列をAに記録しておく
A = [0] * (N + 1)
for _ in range(int(input())):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    L = LCA.LCA(a,b)
    A[a] += 1
    A[b] += 1
    A[L] -= 1
    A[LCA.parent[L]] -= 1  #rootの場合はA[-1]に反映される

#BFS帰りがけ順にクエリを消化
ans = 0
Q = [(0, -1)]
for now,back in Q:
    for nxt in G[now]:
        if nxt != back: Q.append((nxt, now))
while Q:
    now,back = Q.pop()
    ans += A[now] * (A[now] + 1) // 2
    A[back] += A[now]

#答えを出力
print(ans)
0