結果

問題 No.399 動的な領主
コンテスト
ユーザー onakasuitacity
提出日時 2023-05-01 08:23:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,925 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 126,928 KB
最終ジャッジ日時 2024-11-20 09:06:07
合計ジャッジ時間 50,771 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LinkCutTree(object):
    def __init__(self, A, dot, e, compose, id, act):
        n = len(A)
        self._value = A[:]
        self._left = [-1] * n
        self._right = [-1] * n
        self._parent = [-1] * n
        self._size = [1] * n
        self._sum = A[:]
        self._reverse = [False] * n
        self._lazy = [id] * n
        self._dot, self._e, self._compose, self._id, self._act = dot, e, compose, id, act
    
    def _state(self, v):
        if self._parent[v] == -1:
            return 0
        elif self._left[self._parent[v]] == v:
            return -1
        elif self._right[self._parent[v]] == v:
            return 1
        else:
            return 0
    
    def _push(self, v):
        left, right = self._left, self._right
        if self._lazy[v] != self._id:
            lazy, compose, act = self._lazy, self._compose, self._act
            self._value[v] = act(lazy[v], self._value[v], 1)
            self._sum[v] = act(lazy[v], self._sum[v], self._size[v])
            if left[v] != -1:
                lazy[left[v]] = compose(lazy[left[v]], lazy[v])
            if right[v] != -1:
                lazy[right[v]] = compose(lazy[right[v]], lazy[v])
            lazy[v] = self._id
        if self._reverse[v]:
            reverse = self._reverse
            left[v], right[v] = right[v], left[v]
            if left[v] != -1:
                reverse[left[v]] ^= True
            if right[v] != -1:
                reverse[right[v]] ^= True
            reverse[v] = False
    
    def _update(self, v):
        left, right, size, sum = self._left, self._right, self._size, self._sum
        size[v] = 1
        sum[v] = self._value[v]
        if left[v] != -1:
            self._push(left[v])
            size[v] += size[left[v]]
            sum[v] = self._dot(sum[left[v]], sum[v])
        if right[v] != -1:
            self._push(right[v])
            size[v] += size[right[v]]
            sum[v] = self._dot(sum[v], sum[right[v]])
    
    def _rotate(self, v, p, d):
        left, right, parent = self._left, self._right, self._parent
        reverse, lazy = self._reverse, self._lazy
        self._push(v)
        if d == -1:
            left[p] = right[v]
            if right[v] != -1:
                parent[right[v]] = p
            right[v], parent[p] = p, v
        elif d == 1:
            right[p] = left[v]
            if left[v] != -1:
                parent[left[v]] = p
            left[v], parent[p] = p, v
        reverse[v], reverse[p] = reverse[p], False
        lazy[v], lazy[p] = lazy[p], self._id
        self._update(p)
    
    def _splay(self, v):
        left, right, parent = self._left, self._right, self._parent
        state, rotate = self._state, self._rotate
        p, dp = parent[v], state(v)
        while dp:
            g, dg = parent[p], state(p)
            if dg:
                np, ndp = parent[g], state(g)
                if dp == dg:
                    rotate(p, g, dg)
                    rotate(v, p, dp)
                else:
                    rotate(v, p, dp)
                    rotate(v, g, dg)
                p, dp = np, ndp
            else:
                rotate(v, p, dp)
                parent[v] = g
                break
        else:
            parent[v] = p

    def _expose(self, v):
        right, parent = self._right, self._parent
        update, splay, push = self._update, self._splay, self._push
        prev, cur = -1, v
        while cur != -1:
            splay(cur)
            push(cur)
            right[cur] = prev
            prev, cur = cur, parent[cur]
        splay(v)
        update(v)
        return prev
    
    def evert(self, v):
        self._expose(v)
        self._reverse[v] ^= True
    
    def lca(self, u, v):
        self._expose(u)
        return self._expose(v)
    
    def link(self, u, v):
        self.evert(u)
        self._parent[u] = v
    
    def cut(self, v):
        self._expose(v)
        self._parent[self._left[v]] = -1
        self._left[v] = -1
        self._update(v)
    
    def is_connected(self, u, v):
        if u == v:
            return True
        self._expose(u)
        self._expose(v)
        return self._parent[u] != -1
    
    def act(self, u, v, f):
        self.evert(u)
        self._expose(v)
        self._lazy[v] = self._compose(self._lazy[v], f) 
    
    def sum(self, u, v):
        self.evert(u)
        self._expose(v)
        return self._sum[v]


import sys
input = sys.stdin.buffer.readline
from operator import add

N = int(input())
dot = add
e = 0
compose = add
id = 0
act = lambda f, val, size: val + f * size

tree = LinkCutTree([1] * N, dot, e, compose, id, act)
for _ in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    tree.link(u, v)

ans = 0
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    ans += tree.sum(u, v)
    tree.act(u, v, 1)

print(ans)
0