結果

問題 No.650 行列木クエリ
ユーザー SalmonizeSalmonize
提出日時 2020-05-04 11:36:14
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,450 ms / 2,000 ms
コード長 5,326 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 13,440 KB
実行使用メモリ 56,140 KB
最終ジャッジ日時 2024-06-24 00:15:05
合計ジャッジ時間 7,488 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
11,520 KB
testcase_01 AC 645 ms
21,504 KB
testcase_02 AC 1,254 ms
50,048 KB
testcase_03 AC 31 ms
11,392 KB
testcase_04 AC 617 ms
21,376 KB
testcase_05 AC 1,450 ms
50,048 KB
testcase_06 AC 33 ms
11,392 KB
testcase_07 AC 33 ms
11,392 KB
testcase_08 AC 717 ms
22,784 KB
testcase_09 AC 1,342 ms
56,140 KB
testcase_10 AC 34 ms
11,392 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegTree:
    def __init__(self, N, func, ele=0):
        self.N = N
        self.func = func
        self.ele = ele
        self._N = 1<<((N-1).bit_length())
        self.node = [ele]*2*self._N

    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.func(self.node[i*2+1], self.node[i*2+2])
        return

    def update(self,i,x):
        i += self._N-1
        self.node[i] = x
        while i:
            i = (i - 1) >> 1
            self.node[i] = self.func(self.node[i*2+1], self.node[i*2+2])

    def query2(self,p,q,idx=0,a=0,b=None): #[l, r)
        if b is None:
            b = self._N
        if q <= p or b <= p or q <= a:
            return self.ele
        elif p <= a and b <= q:
            return self.node[idx]
        else:
            res1 = self.query2(p,q,idx*2+1,a,(a+b)//2)
            res2 = self.query2(p,q,idx*2+2,(a+b)//2,b)
            return self.func(res1,res2)

    def query(self, left, right): # Non Recursion
        left += self._N
        right += self._N
        ret1 = self.ele
        ret2 = self.ele
        while left < right:
            if left & 1:
                ret1 = self.func(ret1, self.node[left-1])
                left += 1
            if right & 1:
                right -= 1
                ret2 = self.func(self.node[right-1], ret2)
            left, right = left >> 1, right >> 1
        return self.func(ret1, ret2)


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 get_id(self, v):
      return self.vid[v]

    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):
        while True:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
            if self.head[u] != self.head[v]:
                yield (self.vid[self.head[v]], self.vid[v])
                v = self.par[self.head[v]]
            else:
                if u != v:
                    yield (self.vid[u] + 1, self.vid[v])
                break

    def subtree_range(self, v): # Need Repair
        return (self.vid[v], self.rng[v])

      
mod = 10**9 + 7
ele = (1, 0, 0, 1)
def dot(p, q):
    if p == ele:
      return q
    if q == ele:
      return p
    r0 = (p[0]*q[0] + p[1]*q[2]) % mod
    r1 = (p[0]*q[1] + p[1]*q[3]) % mod
    r2 = (p[2]*q[0] + p[3]*q[2]) % mod
    r3 = (p[2]*q[1] + p[3]*q[3]) % mod
    return (r0, r1, r2, r3)
  
n = int(input())
hld = HLDecomposition(n)
edges = [tuple(map(int, input().split())) for _ in range(n-1)]
for u, v in edges:
  hld.add_edge(u, v)
hld.build()
q = int(input())
seg = SegTree(n, dot, ele)
for _ in range(q):
  t, *e = input().split()
  if t == 'x':
    i = int(e[0])
    a = tuple(map(int, e[1:]))
    u, v = edges[i]
    seg.update(max(hld.get_id(u), hld.get_id(v)), a)
  else:
    i, j = map(int, e)
    res = ele
    for u, v in hld.for_each_edge(i, j):
      res = dot(seg.query(u, v+1), res)
    print(*res)
0