結果

問題 No.650 行列木クエリ
ユーザー 前田悠真
提出日時 2025-09-09 00:20:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,275 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 82,424 KB
実行使用メモリ 141,524 KB
最終ジャッジ日時 2025-09-09 00:20:37
合計ジャッジ時間 5,043 ms
ジャッジサーバーID
（参考情報） 		judge / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 1 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

class HLDecomposition:
  def __init__(self, N, G, op, e):
    self.N = N
    self.G = G
    self.op = op
    self.e = e

    self.parent = [-1]*N
    self.depth = [0]*N
    self.size = [0]*N
    self.heavy = [-1]*N

    self.__build_1(0)

    self.top = [0]*N
    self.HLD_G = [0]

    self.__build_2(0)

    self.HLD_G = self.HLD_G[::-1]

    self.node_w = [self.e.copy() for _ in range(N)]
    self.node = [N-1]*N

    self.__make_tree()

  def set(self, v, w, weight):
    if self.parent[w]==v:
      v, w = w, v
    elif self.parent[v]!=w:
      return False
    
    vi, wi = self.node[v], self.node[w]
    self.Tree.set(vi, weight)

  def prod(self, l, r):
    sml, smr = self.e, self.e

    while True:
      li, ri = self.node[l], self.node[r]
      # print(l, r)

      if self.top[l]==self.top[r]:
        if self.depth[l]>self.depth[r]:
          sml = self.op(sml, self.Tree.prod(li, ri))
        else:
          smr = self.op(self.Tree.prod(ri, li), smr)
        
        return self.op(sml, smr)
      else:
        l_top, r_top = self.top[l], self.top[r]

        if self.depth[l_top]>self.depth[r_top]:
          sml = self.op(sml, self.Tree.prod(li, self.node[l_top]+1))
          l = self.parent[l_top]
        else:
          smr = self.op(self.Tree.prod(ri, self.node[r_top]+1), smr)
          r = self.parent[r_top]
  
  def __build_1(self, v0):
    for v1, _ in self.G[v0]:
      if v1==self.parent[v0]:
        continue
      else:
        self.parent[v1] = v0
        self.depth[v1] = self.depth[v0]+1
        self.size[v0] += self.__build_1(v1)

        temp = self.heavy[v0]
        if temp==-1 or self.size[temp]<self.size[v1]:
          self.heavy[v0] = v1
    
    self.size[v0] += 1
    return self.size[v0]
  
  def __build_2(self, v0):
    if self.heavy[v0]!=-1:
      v1 = self.heavy[v0]
      self.top[v1] = self.top[v0]

      self.HLD_G.append(v1)
      self.__build_2(v1)

    for v1, _ in self.G[v0]:
      if v1==self.heavy[v0] or v1==self.parent[v0]:
        continue
      else:
        self.top[v1] = v1
        self.HLD_G.append(v1)
        self.__build_2(v1)
  
  def __make_tree(self):
    for i, v0 in enumerate(self.HLD_G[:-1]):
      for v1, w in self.G[v0]:
        if v1==self.parent[v0]:
          self.node_w[i] = w
          break
      self.node[v0] = i
    
    self.Tree = SegmentTree(self.op, self.e, self.N, self.node_w)
  
class SegmentTree:
  def __init__(self, op, e, n, List=None):
    self.op = op
    self.e = e
    self.n = n
    self.log_2 = (self.n-1).bit_length()
    self.size = 1<<self.log_2
    self.data = [e for _ in range(2*self.size)]

    if not List is None:
      for i in range(self.n):
        self.data[i+self.size] = List[i]
      for i in range(self.size-1, 0, -1):
        self.data[i] = self.op(self.data[i<<1], self.data[(i<<1)|1])
  
  def prod(self, l, r):
    sml, smr = self.e, self.e
    l += self.size
    r += self.size

    while l<r:
      if l&1==1:
        sml = self.op(sml, self.data[l])
        l += 1
      if r&1==1:
        r -= 1
        smr = self.op(self.data[r], smr)
      l >>= 1
      r >>= 1
    return self.op(sml, smr)
  
  def set(self, i, x):
    i += self.size
    self.data[i] = x

    while i>1:
      i >>= 1
      self.data[i] = self.op(self.data[i<<1], self.data[(i<<1)|1])
  
  def get(self, i):
    return self.data[i+self.size]
  
  def all_prod(self):
    return self.data[1]
  
  def max_right(self, l, f):
    if l==self.n:
      return self.n
    
    l += self.size
    sm = self.e

    while True:
      while l&1==0:
        l >>= 1
      
      if not f(self.op(sm, self.data[l])):
        while l<self.size:
          l <<= 1

          if f(self.op(sm, self.data[l])):
            sm = self.op(sm, self.data[l])
            l += 1
        return l-self.size
      else:
        sm = self.op(sm, self.data[l])
        l += 1

        if l&(-l)==l:
          return self.n
    
  def min_left(self, r, f):
    if r==0:
      return 0
    
    r += self.size
    sm = self.e

    while True:
      r -= 1

      while r&1==1 and r>1:
        r >>= 1
      
      if not f(self.op(self.data[r], sm)):
        while r<self.size:
          r <<= 1
          r += 1

          if f(self.op(self.data[r], sm)):
            sm = self.op(self.data[r], sm)
            r -= 1
          
          return r+1-self.size
      else:
        sm = self.op(self.data[r], sm)
        if r&-r==r:
          return 0

n = int(input())
e = [[1, 0], [0, 1]]
G = [[] for _ in range(n)]
UV = [tuple(map(int, input().split())) for _ in range(n-1)]
for i in range(n-1):
  u, v = UV[i]
  G[u].append((v, e.copy()))
  G[v].append((u, e.copy()))

def op(R, L):
  return [[L[0][0]*R[0][0]+L[0][1]*R[1][0], L[0][0]*R[0][1]+L[0][1]*R[1][1]], [L[1][0]*R[0][0]+L[1][1]*R[1][0], L[1][0]*R[0][1]+L[1][1]*R[1][1]]]

HL = HLDecomposition(n, G, op, e)

for _ in range(int(input())):
  it = map(str, input().split())
  if next(it)=='x':
    idx, a, b, c, d = map(int, list(it))
    HL.set(UV[idx][0], UV[idx][1], [[a, b], [c, d]])
  else:
    u, v = map(int, list(it))
    x = HL.prod(v, u)
    answer = []
    for i in range(2):
      for j in range(2):
        answer.append(x[i][j])
    print(*answer)
0