結果

問題 No.399 動的な領主
ユーザー rpy3cpprpy3cpp
提出日時 2016-07-16 00:30:06
言語 PyPy2
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,514 bytes
コンパイル時間 2,149 ms
コンパイル使用メモリ 76,436 KB
実行使用メモリ 353,072 KB
最終ジャッジ日時 2024-10-15 12:57:29
合計ジャッジ時間 13,700 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 75 ms
75,520 KB
testcase_01 AC 75 ms
75,776 KB
testcase_02 AC 123 ms
76,800 KB
testcase_03 AC 80 ms
76,568 KB
testcase_04 AC 123 ms
79,232 KB
testcase_05 AC 257 ms
92,544 KB
testcase_06 AC 867 ms
220,820 KB
testcase_07 AC 873 ms
228,052 KB
testcase_08 AC 786 ms
223,104 KB
testcase_09 AC 757 ms
223,460 KB
testcase_10 AC 135 ms
80,512 KB
testcase_11 AC 198 ms
89,620 KB
testcase_12 AC 598 ms
200,116 KB
testcase_13 AC 618 ms
223,408 KB
testcase_14 MLE -
testcase_15 MLE -
testcase_16 AC 772 ms
289,484 KB
testcase_17 AC 792 ms
221,648 KB
testcase_18 AC 765 ms
219,212 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 i in range(Q):
        a, b = map(int, input().split())
        moves.append((a - 1, b - 1))
    return N, Es, Q, 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, Q, 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)

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):
    tax = 0
    for i3, i2 in zip(imos3, imos2):
        t = i3 + i2
        tax += t * (t + 1) // 2
    return tax



pars = read_data()
print(solve(*pars))
0