結果

問題 No.2340 Triple Tree Query (Easy)
ユーザー NachiaNachia
提出日時 2023-05-30 22:49:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,464 ms / 5,000 ms
コード長 2,732 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 175,632 KB
最終ジャッジ日時 2024-06-08 20:46:41
合計ジャッジ時間 42,475 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,736 KB
testcase_01 AC 182 ms
79,076 KB
testcase_02 AC 187 ms
79,188 KB
testcase_03 AC 187 ms
79,228 KB
testcase_04 AC 188 ms
78,984 KB
testcase_05 AC 202 ms
80,584 KB
testcase_06 AC 1,240 ms
172,784 KB
testcase_07 AC 1,297 ms
171,672 KB
testcase_08 AC 1,243 ms
171,260 KB
testcase_09 AC 1,282 ms
171,676 KB
testcase_10 AC 1,415 ms
175,120 KB
testcase_11 AC 1,415 ms
174,088 KB
testcase_12 AC 1,238 ms
170,472 KB
testcase_13 AC 1,414 ms
174,384 KB
testcase_14 AC 1,358 ms
171,340 KB
testcase_15 AC 1,448 ms
175,632 KB
testcase_16 AC 1,304 ms
164,076 KB
testcase_17 AC 1,441 ms
164,464 KB
testcase_18 AC 1,331 ms
165,616 KB
testcase_19 AC 1,308 ms
164,044 KB
testcase_20 AC 1,464 ms
166,640 KB
testcase_21 AC 962 ms
144,904 KB
testcase_22 AC 967 ms
145,464 KB
testcase_23 AC 953 ms
147,596 KB
testcase_24 AC 1,338 ms
173,216 KB
testcase_25 AC 1,424 ms
174,276 KB
testcase_26 AC 1,420 ms
174,140 KB
testcase_27 AC 1,336 ms
173,060 KB
testcase_28 AC 1,316 ms
173,736 KB
testcase_29 AC 998 ms
147,792 KB
testcase_30 AC 988 ms
146,756 KB
testcase_31 AC 967 ms
147,916 KB
testcase_32 AC 1,231 ms
147,216 KB
testcase_33 AC 1,075 ms
144,448 KB
testcase_34 AC 1,061 ms
144,740 KB
testcase_35 AC 1,192 ms
147,808 KB
testcase_36 AC 1,227 ms
146,896 KB
権限があれば一括ダウンロードができます

ソースコード

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