#901232 (PyPy3) No.2439 Fragile Apple Tree

• 問題: 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

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	AC	1,968 ms; 218,176 KB
testcase_04	AC	3,601 ms; 214,916 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	67 ms; 69,888 KB
testcase_10	AC	68 ms; 70,272 KB
testcase_11	AC	67 ms; 70,292 KB
testcase_12	AC	67 ms; 69,888 KB
testcase_13	AC	67 ms; 70,272 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	AC	70 ms; 69,888 KB
testcase_29	AC	67 ms; 69,760 KB
testcase_30	AC	72 ms; 70,912 KB
testcase_31	WA	-
testcase_32	WA	-

ソースコード

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