結果

問題 No.2340 Triple Tree Query (Easy)
コンテスト
ユーザー Nachia
提出日時 2023-05-30 22:49:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,241 ms / 5,000 ms
コード長 2,732 bytes
コンパイル時間 595 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 175,656 KB
最終ジャッジ日時 2024-12-28 13:15:57
合計ジャッジ時間 56,170 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
def affine(f, x) :
    return [ f[0] * x[0] % MOD , (f[0] * x[1] + f[1]) % MOD ]
class DualSegtree :
    fid = [1,0]
    a = []
    z = 0
    logz = 0
    def init(self, n) :
        self.z = 1
        self.logz = 0
        while self.z < n :
            self.z *= 2
            self.logz += 1
        self.a = [self.fid for _ in range(self.z*2)]
    def mapf(self, p, f) :
        self.a[p] = affine(f, self.a[p])
    def spread(self, p) :
        self.mapf(p*2, self.a[p])
        self.mapf(p*2+1, self.a[p])
        self.a[p] = self.fid
    def spread_path(self, p) :
        d = self.logz
        while d > 0 :
            self.spread(p >> d)
            d -= 1
    def get(self, p) :
        p += self.z
        self.spread_path(p)
        return self.a[p]
    def apply_renge(self, l, r, f) :
        if l >= r :
            return
        if l == 0 and r == self.z :
            self.mapf(1, f)
            return
        l += self.z
        r += self.z
        self.spread_path(l)
        self.spread_path(r-1)
        while l < r :
            if l % 2 == 1 :
                self.mapf(l, f)
                l += 1
            if r % 2 == 1 :
                r -= 1
                self.mapf(r, f)
            l //= 2
            r //= 2
    def apply(self, p, f) :
        p += self.z
        self.spread_path(p)
        self.mapf(p, f)
n, q = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1) :
    u, v = map(int, input().split())
    adj[u-1].append(v-1)
    adj[v-1].append(u-1)
xx = list(map(int,input().split()))
bfs = [0]
par = [-1] * n
sz = [1] * n
for i in range(n) :
    v = bfs[i]
    for w in adj[v] :
        if par[v] != w :
            par[w] = v
            bfs.append(w)
for v in range(1, n) :
    adj[v].remove(par[v])
for v in bfs[n-1 : 0 : -1] :
    sz[par[v]] += sz[v]
dfs = [0] * n
for j in range(n) :
    v = dfs[j]
    p = j + 1
    for w in adj[v] :
        dfs[p] = w
        p += sz[w]
pos = [0] * n
ord = [0]
beg = [0] * n
for v in dfs :
    beg[v] = len(ord)
    for w in adj[v] :
        pos[w] = len(ord)
        ord.append(w)
seg = DualSegtree()
seg.init(n)
for _ in range(q) :
    arg = list(map(int,input().split()))
    if arg[0] == 1 :
        v = arg[1] - 1
        re = seg.get(pos[v])
        ans = (re[0] * xx[v] + re[1]) % MOD
        print(ans, flush=False)
    if arg[0] == 2 :
        v = arg[1] - 1
        ap = [arg[3], arg[4]]
        seg.apply_renge(beg[v], beg[v] + len(adj[v]), ap)
        seg.apply(pos[v], ap)
        if v != 0 :
            seg.apply(pos[par[v]], ap)
    if arg[0] == 3 :
        v = arg[1] - 1
        ap = [arg[2], arg[3]]
        seg.apply(pos[v], ap)
        seg.apply_renge(beg[v], beg[v] + sz[v] - 1, ap)
0