結果

問題 No.399 動的な領主
ユーザー SalmonizeSalmonize
提出日時 2020-05-04 10:55:45
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 6,057 bytes
コンパイル時間 118 ms
コンパイル使用メモリ 13,312 KB
実行使用メモリ 53,924 KB
最終ジャッジ日時 2024-06-23 23:20:30
合計ジャッジ時間 6,882 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
18,332 KB
testcase_01 AC 36 ms
11,392 KB
testcase_02 AC 36 ms
11,392 KB
testcase_03 AC 40 ms
11,520 KB
testcase_04 AC 120 ms
12,032 KB
testcase_05 AC 1,477 ms
17,664 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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0