結果

問題 No.900 aδδitivee
コンテスト
ユーザー toyuzuko
提出日時 2020-05-15 20:57:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 772 ms / 2,000 ms
コード長 4,986 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 82,956 KB
実行使用メモリ 127,700 KB
最終ジャッジ日時 2024-09-19 07:44:15
合計ジャッジ時間 17,726 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Tree(): #weighted
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0]].append((e[1], e[2]))
            self.tree[e[1]].append((e[0], e[2]))

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.distance = [None for _ in range(self.n)]
        self.distance[root] = 0
        self.order = []
        self.order.append(root)
        self.cost = [0 for _ in range(self.n)]
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj, cost in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.distance[adj] = self.distance[node] + cost
                    self.cost[adj] = cost
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj, cost in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def heavylight_decomposition(self):
        self.order = [None for _ in range(self.n)]
        self.head = [None for _ in range(self.n)]
        self.head[self.root] = self.root
        self.next = [None for _ in range(self.n)]
        stack = [self.root]
        order = 0
        while stack:
            node = stack.pop()
            self.order[node] = order
            order += 1
            maxsize = 0
            for adj, cost in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                if maxsize < self.size[adj]:
                    maxsize = self.size[adj]
                    self.next[node] = adj
            for adj, cost in self.tree[node]:
                if self.parent[node] == adj or self.next[node] == adj:
                    continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[node] is not None:
                self.head[self.next[node]] = self.head[node]
                stack.append(self.next[node])

    def range_hld(self, u, v, edge=False):
        res = []
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                res.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.parent[self.head[v]]
            else:
                res.append((self.order[u] + edge, self.order[v] + 1))
                return res

    def subtree_hld(self, u, edge=False):
        return self.order[u] + edge, self.order[u] + self.size[u]

    def lca_hld(self, u, v):
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                v = self.parent[self.head[v]]
            else:
                return u

class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1

class RAQandRSQ():
    def __init__(self, n):
        self.bit1 = BinaryIndexedTree(n)
        self.bit2 = BinaryIndexedTree(n)

    def add(self, lt, rt, x):
        self.bit1.add(lt + 1, -x * (lt))
        self.bit1.add(rt + 1, x * (rt))
        self.bit2.add(lt + 1, x)
        self.bit2.add(rt + 1, -x)

    def sum(self, lt, rt):
        rsum = self.bit2.sum(rt) * (rt) + self.bit1.sum(rt)
        lsum = self.bit2.sum(lt) * (lt) + self.bit1.sum(lt)
        return rsum - lsum

import sys
input = sys.stdin.readline

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

T = Tree(N, E)
T.setroot(0)
T.heavylight_decomposition()

R = RAQandRSQ(N)

for i in range(N):
    R.add(T.order[i], T.order[i] + 1, T.cost[i])

Q = int(input())
res = list()

for _ in range(Q):
    q = tuple(map(int, input().split()))
    if q[0] == 1:
        a, x = q[1:]
        lt, rt = T.subtree_hld(a, True)
        R.add(lt, rt, x)
    else:
        b = q[1]
        s = 0
        for lt, rt in T.range_hld(0, b, True):
            s += R.sum(lt, rt)
        res.append(s)

print('\n'.join(map(str, res)))
0