結果

問題 No.2340 Triple Tree Query (Easy)
ユーザー 👑 NachiaNachia
提出日時 2023-05-30 22:49:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,601 ms / 5,000 ms
コード長 2,732 bytes
コンパイル時間 267 ms
コンパイル使用メモリ 87,284 KB
実行使用メモリ 179,608 KB
最終ジャッジ日時 2023-08-28 01:13:19
合計ジャッジ時間 46,371 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
71,344 KB
testcase_01 AC 232 ms
80,772 KB
testcase_02 AC 236 ms
80,688 KB
testcase_03 AC 220 ms
79,936 KB
testcase_04 AC 224 ms
80,700 KB
testcase_05 AC 240 ms
81,676 KB
testcase_06 AC 1,428 ms
175,144 KB
testcase_07 AC 1,404 ms
175,760 KB
testcase_08 AC 1,390 ms
177,028 KB
testcase_09 AC 1,367 ms
176,544 KB
testcase_10 AC 1,569 ms
178,192 KB
testcase_11 AC 1,579 ms
176,904 KB
testcase_12 AC 1,379 ms
175,368 KB
testcase_13 AC 1,553 ms
179,608 KB
testcase_14 AC 1,372 ms
176,828 KB
testcase_15 AC 1,601 ms
178,972 KB
testcase_16 AC 1,440 ms
167,464 KB
testcase_17 AC 1,498 ms
167,656 KB
testcase_18 AC 1,436 ms
167,712 KB
testcase_19 AC 1,399 ms
167,008 KB
testcase_20 AC 1,451 ms
167,712 KB
testcase_21 AC 1,010 ms
149,236 KB
testcase_22 AC 1,009 ms
149,348 KB
testcase_23 AC 1,014 ms
147,676 KB
testcase_24 AC 1,448 ms
174,420 KB
testcase_25 AC 1,570 ms
176,460 KB
testcase_26 AC 1,581 ms
176,944 KB
testcase_27 AC 1,424 ms
175,184 KB
testcase_28 AC 1,420 ms
175,248 KB
testcase_29 AC 1,076 ms
151,232 KB
testcase_30 AC 1,055 ms
150,984 KB
testcase_31 AC 1,070 ms
149,216 KB
testcase_32 AC 1,372 ms
151,120 KB
testcase_33 AC 1,197 ms
148,696 KB
testcase_34 AC 1,169 ms
148,420 KB
testcase_35 AC 1,322 ms
151,740 KB
testcase_36 AC 1,320 ms
148,860 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