結果

問題 No.2340 Triple Tree Query (Easy)
ユーザー 👑 NachiaNachia
提出日時 2023-05-30 22:46:05
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,728 bytes
コンパイル時間 1,092 ms
コンパイル使用メモリ 86,512 KB
実行使用メモリ 178,724 KB
最終ジャッジ日時 2023-08-28 01:12:13
合計ジャッジ時間 32,926 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
71,324 KB
testcase_01 RE -
testcase_02 AC 228 ms
80,588 KB
testcase_03 RE -
testcase_04 RE -
testcase_05 AC 238 ms
81,548 KB
testcase_06 RE -
testcase_07 AC 1,377 ms
175,524 KB
testcase_08 AC 1,329 ms
177,356 KB
testcase_09 RE -
testcase_10 AC 1,582 ms
178,424 KB
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 AC 1,388 ms
176,632 KB
testcase_15 AC 1,547 ms
178,724 KB
testcase_16 AC 1,356 ms
167,688 KB
testcase_17 AC 1,433 ms
167,572 KB
testcase_18 RE -
testcase_19 AC 1,386 ms
167,200 KB
testcase_20 AC 1,458 ms
167,716 KB
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 AC 1,481 ms
174,464 KB
testcase_25 RE -
testcase_26 WA -
testcase_27 AC 1,471 ms
175,164 KB
testcase_28 AC 1,438 ms
175,136 KB
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
権限があれば一括ダウンロードができます

ソースコード

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 reversed(bfs) :
    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