結果
| 問題 | No.399 動的な領主 |
| ユーザー |
 toyuzuko
|
| 提出日時 | 2020-05-09 21:52:47 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,603 bytes |
| コンパイル時間 | 313 ms |
| コンパイル使用メモリ | 86,400 KB |
| 実行使用メモリ | 186,588 KB |
| 最終ジャッジ日時 | 2023-09-20 09:23:37 |
| 合計ジャッジ時間 | 6,334 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 78 ms
71,640 KB |
| testcase_01 | AC | 76 ms
70,860 KB |
| testcase_02 | AC | 106 ms
76,460 KB |
| testcase_03 | AC | 107 ms
76,896 KB |
| testcase_04 | AC | 271 ms
80,456 KB |
| testcase_05 | AC | 508 ms
88,708 KB |
| testcase_06 | TLE | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
ソースコード
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 SegmentTreeLazy():
def __init__(self, arr, ti, ei, func, op, merge):
self.h = (len(arr) - 1).bit_length()
self.n = 2**self.h
self.func = func
self.op = op
self.merge = merge
self.ti = ti
self.ei = ei
self.val = [ti for _ in range(2 * self.n)]
for i in range(len(arr)):
self.val[self.n + i] = arr[i]
for i in range(1, self.n)[::-1]:
self.val[i] = self.func(self.val[2 * i], self.val[2 * i + 1])
self.laz = [ei for _ in range(2 * self.n)]
def reflect(self, k):
if self.laz[k] == self.ei:
return self.val[k]
return self.op(self.val[k], self.laz[k])
def propagate(self, k):
if self.laz[k] == self.ei: return
self.laz[2 * k] = self.merge(self.laz[2 * k], self.laz[k])
self.laz[2 * k + 1] = self.merge(self.laz[2 * k + 1], self.laz[k])
self.val[k] = self.reflect(k)
self.laz[k] = self.ei
def thrust(self, k):
for i in range(1, self.h + 1)[::-1]:
self.propagate(k >> i)
def recalc(self, k):
while k:
k >>= 1
self.val[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1))
def update(self, lt, rt, x):
lt += self.n
rt += self.n
vl = lt
vr = rt
self.thrust(lt)
self.thrust(rt - 1)
while rt - lt > 0:
if lt & 1:
self.laz[lt] = self.merge(self.laz[lt], x)
lt += 1
if rt & 1:
rt -= 1
self.laz[rt] = self.merge(self.laz[rt], x)
lt >>= 1
rt >>= 1
self.recalc(vl)
self.recalc(vr - 1)
def query(self, lt, rt):
lt += self.n
rt += self.n
self.thrust(lt)
self.thrust(rt - 1)
vl = vr = self.ti
while rt - lt > 0:
if lt & 1:
vl = self.func(vl, self.reflect(lt))
lt += 1
if rt & 1:
rt -= 1
vr = self.func(self.reflect(rt), vr)
lt >>= 1
rt >>= 1
return self.func(vl, vr)
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()
st = SegmentTreeLazy(
arr = [(0, 1) for _ in range(N)],
ti = (0, 1),
ei = 0,
func = lambda a, b: (a[0] + b[0], a[1] + b[1]),
op = lambda a, x: (a[0] + a[1] * x, a[1]),
merge = lambda x, y : x + y
)
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):
st.update(lt, rt, 1)
res += st.query(lt, rt)[0]
print(res)