結果

問題 No.2340 Triple Tree Query (Easy)
ユーザー 👑 NachiaNachia
提出日時 2023-05-30 22:46:05
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,728 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 175,492 KB
最終ジャッジ日時 2024-06-08 20:45:36
合計ジャッジ時間 29,024 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
52,352 KB
testcase_01 RE -
testcase_02 AC 190 ms
79,316 KB
testcase_03 RE -
testcase_04 RE -
testcase_05 AC 203 ms
80,360 KB
testcase_06 RE -
testcase_07 AC 1,266 ms
171,544 KB
testcase_08 AC 1,292 ms
171,020 KB
testcase_09 RE -
testcase_10 AC 1,436 ms
175,492 KB
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 AC 1,252 ms
171,532 KB
testcase_15 AC 1,450 ms
175,304 KB
testcase_16 AC 1,287 ms
164,332 KB
testcase_17 AC 1,318 ms
164,192 KB
testcase_18 RE -
testcase_19 AC 1,308 ms
164,180 KB
testcase_20 AC 1,369 ms
166,504 KB
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 AC 1,328 ms
173,080 KB
testcase_25 RE -
testcase_26 WA -
testcase_27 AC 1,316 ms
173,052 KB
testcase_28 AC 1,298 ms
173,296 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