結果

問題 No.399 動的な領主
ユーザー rpy3cpprpy3cpp
提出日時 2016-07-16 00:44:33
言語 PyPy2
(7.3.15)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,527 bytes
コンパイル時間 2,420 ms
コンパイル使用メモリ 76,544 KB
実行使用メモリ 350,348 KB
最終ジャッジ日時 2024-04-25 08:50:18
合計ジャッジ時間 14,642 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 90 ms
75,776 KB
testcase_01 AC 91 ms
75,776 KB
testcase_02 AC 99 ms
76,928 KB
testcase_03 AC 96 ms
76,544 KB
testcase_04 AC 130 ms
78,848 KB
testcase_05 AC 270 ms
91,904 KB
testcase_06 AC 904 ms
223,380 KB
testcase_07 AC 901 ms
224,140 KB
testcase_08 AC 825 ms
220,980 KB
testcase_09 AC 802 ms
231,104 KB
testcase_10 AC 143 ms
79,488 KB
testcase_11 AC 208 ms
91,392 KB
testcase_12 AC 622 ms
207,656 KB
testcase_13 AC 633 ms
224,732 KB
testcase_14 MLE -
testcase_15 MLE -
testcase_16 AC 824 ms
290,804 KB
testcase_17 AC 852 ms
223,864 KB
testcase_18 AC 873 ms
219,692 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
sys.setrecursionlimit(10**6)

input = raw_input
range = xrange


def read_data():
    N = int(input())
    Es = [[] for i in range(N)]
    for i in range(N - 1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        Es[u].append(v)
        Es[v].append(u)
    Q = int(input())
    moves = []
    for line in sys.stdin:
        a, b = map(int, line.split())
        moves.append((a - 1, b - 1))
    return N, Es, moves


class Tree():
    def __init__(self, N, Es, root):
        self.n = N
        self.root = root
        self.child = [[] for i in range(N)]
        self._set_child(Es)
    
    def _set_child(self, Es):
        que = [self.root]
        visited = [False] * self.n
        while que:
            v = que.pop()
            for u in Es[v]:
                if visited[u]:
                    continue
                self.child[v].append(u)
                que.append(u)
            visited[v] = True        

class LCArmq():
    def __init__(self, tree):
        D, E, R = self._convert_to_RMQ(tree.child, tree.root, tree.n)
        self._euler = E
        self._reverse = R
        self._RMQ = RMQ(D)

    def _convert_to_RMQ(self, child, root, n):
        ''' LCA の前処理。 RMQ に置き換えるため、Euler tour で巡回して深さのリストをつくる。
        '''
        depth = []
        euler = []
        reverse = [0] * n
        
        def euler_tour(node, d, depth, euler):
            for v in child[node]:
                euler.append(node)
                depth.append(d)
                euler_tour(v, d + 1, depth, euler)
            euler.append(node)
            depth.append(d)

        euler_tour(root, 0, depth, euler)
        for i, node in enumerate(euler):
            reverse[node] = i
        return depth, euler, reverse

    def query(self, v, w):
        i, j = self._reverse[v], self._reverse[w]
        rmq = self._RMQ.query(i, j)
        lca = self._euler[rmq]
        return lca


class RMQ():
    def __init__(self, A):
        self._A = A
        self._preprocess()

    def _preprocess(self):
        ''' RMQ の前処理。
        '''
        n = len(self._A)
        max_j = int(math.log(n, 2))
        self._M = [list(range(n))]
        for j in range(0, max_j):
            shift = 1 << j
            Mj = self._M[j]
            Mjnext = []
            for k1, k2 in zip(Mj, Mj[shift:]):
                k = k1 if self._A[k1] < self._A[k2] else k2
                Mjnext.append(k)
            self._M.append(Mjnext)

    def query(self, i, j):
        if i == j: return i
        if i > j: i, j = j, i
        el = int(math.log(j - i, 2))
        k1 = self._M[el][i]
        k2 = self._M[el][j - (1 << el) + 1]
        rmq = k1 if self._A[k1] < self._A[k2] else k2
        return rmq


def solve(N, Es, moves):
    global imos1, imos2, imos3
    tree = Tree(N, Es, 0)
    lca_rmq = LCArmq(tree)
    imos1 = [0] * N
    imos2 = [0] * N
    for a, b in moves:
        v = lca_rmq.query(a, b)
        imos1[a] += 1
        imos1[b] += 1
        imos1[v] -= 2
        imos2[v] += 1
    imos3 = [0] * N
    dfs(0, tree.child)
    return count_tax(imos3, imos2, N)

def dfs(u, child):
    global imos3
    ret = imos1[u]
    for v in child[u]:
        ret += dfs(v, child)
    imos3[u] = ret
    return ret

def count_tax(imos3, imos2, N):
    tax = 0
    for i in range(N):
        t = imos3[i] + imos2[i]
        tax += t * (t + 1)
    return tax // 2


N, Es, moves = read_data()
print(solve(N, Es, moves))
0