結果

問題 No.399 動的な領主
ユーザー toyuzukotoyuzuko
提出日時 2020-05-09 22:35:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,643 ms / 2,000 ms
コード長 4,340 bytes
コンパイル時間 421 ms
コンパイル使用メモリ 87,084 KB
実行使用メモリ 121,108 KB
最終ジャッジ日時 2023-09-20 09:36:03
合計ジャッジ時間 16,580 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
71,100 KB
testcase_01 AC 73 ms
71,532 KB
testcase_02 AC 87 ms
75,792 KB
testcase_03 AC 78 ms
75,868 KB
testcase_04 AC 141 ms
78,844 KB
testcase_05 AC 266 ms
82,640 KB
testcase_06 AC 1,591 ms
113,580 KB
testcase_07 AC 1,575 ms
113,440 KB
testcase_08 AC 1,603 ms
114,120 KB
testcase_09 AC 1,594 ms
113,896 KB
testcase_10 AC 138 ms
78,828 KB
testcase_11 AC 232 ms
82,576 KB
testcase_12 AC 1,184 ms
113,052 KB
testcase_13 AC 1,163 ms
112,216 KB
testcase_14 AC 332 ms
121,108 KB
testcase_15 AC 372 ms
112,648 KB
testcase_16 AC 626 ms
112,832 KB
testcase_17 AC 1,643 ms
113,852 KB
testcase_18 AC 1,633 ms
113,404 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append(e[1] - 1)
            self.tree[e[1] - 1].append(e[0] - 1)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def heavylight_decomposition(self):
        self.order = [None for _ in range(self.n)]
        self.head = [None for _ in range(self.n)]
        self.head[self.root] = self.root
        self.next = [None for _ in range(self.n)]
        stack = [self.root]
        order = 0
        while stack:
            node = stack.pop()
            self.order[node] = order
            order += 1
            maxsize = 0
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                if maxsize < self.size[adj]:
                    maxsize = self.size[adj]
                    self.next[node] = adj
            for adj in self.tree[node]:
                if self.parent[node] == adj or self.next[node] == adj:
                    continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[node] is not None:
                self.head[self.next[node]] = self.head[node]
                stack.append(self.next[node])

    def range_hld(self, u, v, edge=False):
        res = []
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                res.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.parent[self.head[v]]
            else:
                res.append((self.order[u] + edge, self.order[v] + 1))
                return res

    def lca_hld(self, u, v):
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            v = self.parent[self.head[v]]
        return u

class BinaryIndexedTree(): #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1

class RAQandRSQ(): #1-indexed, BinaryIndexedTree
    def __init__(self, n):
        self.bit1 = BinaryIndexedTree(n)
        self.bit2 = BinaryIndexedTree(n)

    def add(self, lt, rt, x):
        self.bit1.add(lt, -x * (lt - 1))
        self.bit1.add(rt, x * (rt - 1))
        self.bit2.add(lt, x)
        self.bit2.add(rt, -x)

    def sum(self, lt, rt):
        rsum = self.bit2.sum(rt - 1) * (rt - 1) + self.bit1.sum(rt - 1)
        lsum = self.bit2.sum(lt - 1) * (lt - 1) + self.bit1.sum(lt - 1)
        return rsum - lsum

import sys
input = sys.stdin.readline

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

T = Tree(N, E)
T.setroot(0)
T.heavylight_decomposition()
R = RAQandRSQ(N)

Q = int(input())
res = 0

for _ in range(Q):
    a, b = map(int, input().split())
    for lt, rt in T.range_hld(a - 1, b - 1):
        R.add(lt + 1, rt + 1, 1)
        res += R.sum(lt + 1, rt + 1)

print(res)
0