結果
| 問題 |
No.399 動的な領主
|
| コンテスト | |
| ユーザー |
 Salmonize
|
| 提出日時 | 2020-05-04 10:56:35 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,057 bytes |
| コンパイル時間 | 339 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 109,728 KB |
| 最終ジャッジ日時 | 2024-06-23 23:21:03 |
| 合計ジャッジ時間 | 5,269 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 6 TLE * 1 -- * 12 |
ソースコード
class LazySegTree:
def __init__(self, N):
self.N = N
self._N = 1 << ((N - 1).bit_length())
self.Vele = 0
self.Eele = 0
self.node = [0] * 2 * self._N
self.lazy = [0] * 2 * self._N
self.F = lambda x, y: x + y
self.G = lambda v, E, idx: v + E * (self._N >> (idx+1).bit_length() - 1)
self.H = lambda p, q: p + q
def build(self, lis):
for i in range(self.N):
self.node[i + self._N - 1] = lis[i]
for i in range(self._N - 2, -1, -1):
self.node[i] = self.F(self.node[i * 2 + 1], self.node[i * 2 + 2])
def _gindex(self, l, r):
left = l + self._N
right = r + self._N
lm = (left // (left & -left)) >> 1
rm = (right // (right & -right)) >> 1
while left < right:
if right <= rm:
yield right
if left <= lm:
yield left
left >>= 1
right >>= 1
while left:
yield left
left >>= 1
def propagates(self, *ids): # ids: 1-indexded
for i in reversed(ids):
E = self.lazy[i - 1]
if E is self.Eele:
continue
self.lazy[2 * i - 1] = self.H(self.lazy[2 * i - 1], E)
self.node[2 * i - 1] = self.G(self.node[2 * i - 1], E, 2 * i - 1)
self.lazy[2 * i] = self.H(self.lazy[2 * i], E)
self.node[2 * i] = self.G(self.node[2 * i], E, 2 * i + 1)
self.lazy[i - 1] = self.Eele
return
def update(self, l, r, E):
*ids, = self._gindex(l, r)
self.propagates(*ids)
left = l + self._N
right = r + self._N
while left < right:
if left & 1:
self.lazy[left - 1] = self.H(self.lazy[left - 1], E)
self.node[left - 1] = self.G(self.node[left - 1], E, left - 1)
left += 1
if right & 1:
right -= 1
self.lazy[right - 1] = self.H(self.lazy[right - 1], E)
self.node[right - 1] = self.G(self.node[right - 1], E, right - 1)
left >>= 1
right >>= 1
for i in ids:
self.node[i - 1] = self.F(self.node[2 * i - 1], self.node[2 * i])
def query(self, l, r):
self.propagates(*self._gindex(l, r))
left = l + self._N
right = r + self._N
retl = self.Vele
retr = self.Vele
while left < right:
if right & 1:
right -= 1
retr = self.F(self.node[right - 1], retr)
if left & 1:
retl = self.F(retl, self.node[left - 1])
left += 1
left >>= 1
right >>= 1
return self.F(retl, retr)
class HLDecomposition:
def __init__(self, N):
self.N = N
self.pos = 0
self.G = [list() for _ in range(N)]
self.vid = [-1] * N
self.head = [0] * N
self.sub = [1] * N
self.hvy = [-1] * N
self.par = [-1] * N
self.dep = [0] * N
self.inv = [0] * N
self.rng = [0] * N # subtree of v -> [vid[v], rng[v])
def add_edge(self, u, v):
self.G[u].append(v)
self.G[v].append(u)
return
def build(self, rs = (0, )):
for r in rs:
self._dfs(r)
self._dfs_hld(r)
return
def _dfs(self, rt):
self.par[rt] = -1
self.dep[rt] = 0
st = list(); st.append([rt, 0])
while st:
v, i = st[-1]
if i < len(self.G[v]):
u = self.G[v][i]
st[-1][1] += 1
if u == self.par[v]:
continue
self.par[u] = v
self.dep[u] = self.dep[v] + 1
st.append([u, 0])
else:
st.pop()
res = 0
for u in self.G[v]:
if u == self.par[v]:
continue
self.sub[v] += self.sub[u]
if res < self.sub[u]:
res = self.sub[u]
self.hvy[v] = u
return
def _dfs_hld(self, r):
q = [r]
while q:
v = q[-1]
if self.vid[v] < 0:
self.vid[v] = self.pos
self.pos += 1
self.inv[self.vid[v]] = v
self.head[v] = v
if self.hvy[self.par[v]] == v:
self.head[v] = self.head[self.par[v]]
for u in self.G[v]:
if u != self.par[v] and u != self.hvy[v]:
q.append(u)
if self.hvy[v] >= 0:
q.append(self.hvy[v])
else:
q.pop()
self.rng[v] = self.pos
return
def for_each_vertex(self, u, v):
while True:
if self.vid[u] > self.vid[v]:
u, v = v, u
yield (max(self.vid[self.head[v]], self.vid[u]), self.vid[v])
if self.head[u] != self.head[v]:
v = self.par[self.head[v]]
else:
break
return
# [u, v]
def for_each_edge(self, u, v, func):
while True:
if self.vid[u] > self.vid[v]:
u, v = v, u
if self.head[u] != self.head[v]:
func(self.vid[self.head[v]], self.vid[v])
v = self.par[self.head[v]]
elif u != v:
func(self.vid[u] + 1, self.vid[v])
break
return
def subtree_range(self, v): # Need Repair
return (self.vid[v], self.rng[v])
n = int(input())
hld = HLDecomposition(n)
for _ in range(n-1):
u, v = map(int, input().split())
hld.add_edge(u-1, v-1)
hld.build()
q = int(input())
seg = LazySegTree(n)
res = 0
for _ in range(q):
a, b = map(int, input().split())
for u, v in hld.for_each_vertex(a-1, b-1):
seg.update(u, v+1, 1)
res += seg.query(u, v+1)
print(res)