結果

問題 No.2439 Fragile Apple Tree
ユーザー tassei903
提出日時 2023-08-12 01:59:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 13,413 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,760 KB
実行使用メモリ 234,380 KB
最終ジャッジ日時 2024-11-22 12:45:15
合計ジャッジ時間 87,937 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
"""Buggy! the output of practice_k becomes about 1/4."""
from typing import Callable, List, TypeVar
S = TypeVar("S")
F = TypeVar("F")
MOD = 998244353
class LazySegmentTree:
    """Lazy Segment Tree
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
    """
    __slots__ = [
        "e",
        "op",
        "id",
        "mapping",
        "composition",
        "_n",
        "_log",
        "_size",
        "tree",
        "lazy",
    ]
    def __init__(
        self,
        a: List[S],
        e: S,
        op: Callable[[S, S], S],
        id_: F,
        mapping: Callable[[F, S], S],
        composition: Callable[[F, F], F],
    ) -> None:
        self.e = e
        self.op = op
        self.id = id_
        self.mapping = mapping
        self.composition = composition
        self._n = len(a)
        self._log = (self._n - 1).bit_length()
        self._size = 1 << self._log
        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)
        self.lazy = [id_] * self._size
    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])
    def _apply_all(self, k: int, f: F) -> None:
        self.tree[k] = self.mapping(f, self.tree[k])
        if k < self._size:
            self.lazy[k] = self.composition(f, self.lazy[k])
    def _push(self, k: int) -> None:
        self._apply_all(2 * k, self.lazy[k])
        self._apply_all(2 * k + 1, self.lazy[k])
        self.lazy[k] = self.id
    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n
        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = x
        while k:
            k >>= 1
            self._update(k)
    def get(self, k: int) -> S:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        return self.tree[k]
    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n
        if l == r:
            return self.e
        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push(r >> i)
        sml, smr = self.e, self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)
    def prod_all(self) -> S:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]
    def apply(self, k: int, f: F) -> None:
        """Apply a[p] = op_st(a[p], x) in O(log n)."""
        assert 0 <= k < self._n
        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = self.mapping(f, self.tree[k])
        for i in range(1, self._log + 1):
            self._update(k >> i)
    def apply_range(self, l: int, r: int, f: F) -> None:
        """Apply a[i] = op_st(a[i], x) for all i = l..r-1 in O(log n)."""
        assert 0 <= l <= r <= self._n
        if l == r:
            return
        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push((r - 1) >> i)
        l_tmp, r_tmp = l, r
        while l < r:
            if l & 1:
                self._apply_all(l, f)
                l += 1
            if r & 1:
                r -= 1
                self._apply_all(r, f)
            l >>= 1
            r >>= 1
        l, r = l_tmp, r_tmp
        for i in range(1, self._log + 1):
            if ((l >> i) << i) != l:
                self._update(l >> i)
            if ((r >> i) << i) != r:
                self._update((r - 1) >> i)
    def max_right(self, l: int, g: Callable[[S], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.
        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.
        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert g(self.e)
        if l == self._n:
            return self._n
        l += self._size
        for i in range(self._log, 0, -1):
            self._push(l >> i)
        sm = self.e
        while True:
            while not l & 1:
                l >>= 1
            if not g(self.op(sm, self.tree[l])):
                while l < self._size:
                    l *= 2
                    if g(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self._size
            sm = self.op(sm, self.tree[l])
            l += 1
            if (l & -l) == l:
                break
        return self._n
    def min_left(self, r: int, g: Callable[[S], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.
        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert g(self.e)
        if not r:
            return 0
        r += self._size
        for i in range(self._log, 0, -1):
            self._push((r - 1) >> i)
        sm = self.e
        while True:
            r -= 1
            while r > 1 and r & 1:
                r >>= 1
            if not g(self.op(self.tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if g(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self._size
            sm = self.op(self.tree[r], sm)
            if (r & -r) == r:
                break
        return 0
    
    def nibutan(self, l: int, r: int, g: Callable[[S], bool]) -> int:
        if self.prod(l, r) > 0:
            return -1
        return self.min_left(r, g)
class HeavyLightDecomposition(object):
    def __init__(self, G, root=0):
        N = len(G)
        self._par = [-1] * N
        self._size = [1] * N
        self._heavy_child = [-1] * N
        self._head = [0] * N
        self._order = [0] * N
        self._dfs_heavy_child(G, root)
        self._dfs_decomposition(G, root)
    
    def _dfs_heavy_child(self, G, root):
        par, size, heavy_child = self._par, self._size, self._heavy_child
        stack = [~root, root]
        while stack:
            v = stack.pop()
            if v >= 0:
                for nv in G[v]:
                    if nv != par[v]:
                        par[nv] = v
                        stack.append(~nv)
                        stack.append(nv)
            else:
                v = ~v
                if par[v] != -1:
                    size[par[v]] += size[v]
                for nv in G[v]:
                    if nv == par[v]:
                        continue
                    if heavy_child[v] == -1 or size[nv] > size[heavy_child[v]]:
                        heavy_child[v] = nv
    
    def _dfs_decomposition(self, G, root):
        par, size, heavy_child = self._par, self._size, self._heavy_child
        head, order = self._head, self._order
        stack = [root]
        count = 0
        while stack:
            v = stack.pop()
            order[v] = count
            count += 1
            if order[par[v]] == order[v] - 1:
                head[v] = head[par[v]]
            else:
                head[v] = v
            for nv in G[v]:
                if nv != par[v] and nv != heavy_child[v]:
                    stack.append(nv)
            if heavy_child[v] != -1:
                stack.append(heavy_child[v])
    
    def lca(self, u, v):
        par, head, order = self._par, self._head, self._order
        while True:
            if order[u] > order[v]:
                u, v = v, u
            if head[u] == head[v]:
                return u
            v = par[head[v]]
    def _ascend(self, u, v):
        par, head, order = self._par, self._head, self._order
        res = []
        while head[u] != head[v]:
            res.append((order[u], order[head[u]]))
            u = par[head[u]]
        if u != v:
            res.append((order[u], order[v] + 1))
        return res
    
    def _descend(self, u, v):
        return [(j, i) for i, j in self._ascend(v, u)[::-1]]
    
    def path(self, u, v, edge=False):
        l = self.lca(u, v)
        return self._ascend(u, l) + ([] if edge else [(self._order[l], self._order[l])]) + self._descend(l, v)
    
    def get_order(self):
        return self._order
    
    def edge_to_order(self, E):
        par, order = self._par, self._order
        return [order[u] if par[u] == v else order[v] for u, v in E]
class DualSegmentTree:
    def __init__(self, size, f, default):
        self.n = (size-1).bit_length()
        self.size = 1<<self.n
        self.default = default
        self.lazy = [default]*(self.size*2)
        self.f = f
    def propagate(self, k):
        lazy = self.lazy
        if lazy[k] != self.default:
            lazy[2*k] = self.f(lazy[2*k], lazy[k])
            lazy[2*k+1] = self.f(lazy[2*k+1], lazy[k])
            lazy[k] = self.default
    def thrust(self, k):
        for i in range(self.n,0,-1):
            self.propagate(k>>i)
    def update(self, a, b, x):
        a += self.size
        b += self.size-1
        self.thrust(a)
        self.thrust(b)
        l = a
        r = b + 1
        lazy = self.lazy
        while l < r:
            if l & 1:
                lazy[l] = self.f(lazy[l], x)
                l += 1
            if r & 1:
                r -= 1
                lazy[r] = self.f(lazy[r], x)
            l >>= 1
            r >>= 1
    
    def get(self, k):
        k += self.size
        self.thrust(k)
        return self.lazy[k]
N, Q = map(int, input().split())
_A = [10**18] * N
G = [[] for _ in range(N)]
E = []
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u-=1
    v-=1
    G[u].append(v)
    G[v].append(u)
    E.append((u, v, w))
hld = HeavyLightDecomposition(G)
for u,v,w in E:
    #print(u,v,hld._par[u])
    if hld._par[u] == v:
        _A[u] = w
    else:
        _A[v] = w
order = hld.get_order()
A = [0] * N
t = 0
for i, a in zip(order, _A):
    A[i] = a
# (a dot b)(x) = b(a(x))
# bh(ahx + al) + bl = ahbhx + albh + bl
def dot1(a, b):
    ah, al = divmod(a, MOD)
    bh, bl = divmod(b, MOD)
    return (ah * bh % MOD) * MOD + (al * bh + bl) % MOD
dot2 = lambda a, b: dot1(b, a)
##############################
e = 10**18
id_ = 0
def op(s, t):
    return min(s, t)
def mapping(f, a):
    return a + f
def composition(f, g):
    return f + g
##############################
  
tree1 = LazySegmentTree(A, e, op, id_, mapping, composition)
tree2 = DualSegmentTree(N, lambda x, y: x + y, 0)
for i in range(N):
    j = order[i]
    tree2.update(j, j+1, hld._size[i])
for _ in range(Q):
    t, *aa = map(int, input().split())
    if t == 1:
        v, x = aa
        v -= 1
        y = (10**18, 10**9)
        pt = hld.path(0, v)
        for i, j in pt[::-1]:
            if i <= j:
                tree1.apply_range(i, j+1, -x)
            else:
                tree1.apply_range(j, i+1, -x)
        w = -2
        for i, j in pt[::-1]:
            if i <= j:
                v = tree1.nibutan(i, j+1, lambda x:x > 0)
            else:
                v = tree1.nibutan(j, i+1, lambda x:x > 0)
            if v != -2:
                w = v-1
                break
        if w == -2:continue
        z = tree2.get(w)
        for i, j in pt:
            if i <= j:
                tree2.update(i, j+1, -z)
            else:
                tree2.update(j, i+1, -z)
        c = 10**18
        for i, j in hld.path(0, w):
            if i <= j:
                c = min(c, tree1.prod(i, j+1))
            else:
                c = min(c, tree1.prod(j, i+1))
        b = A[w] - c
        for i, j in hld.path(0, w):
            if i <= j:
                v = tree1.apply_range(i, j+1, b)
            else:
                v = tree1.apply_range(j, i+1, b)
            
    elif t == 2:
        print(tree2.get(0))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0