結果
問題 | No.2340 Triple Tree Query (Easy) |
ユーザー | vjudge1 |
提出日時 | 2024-10-15 13:33:38 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,467 bytes |
コンパイル時間 | 2,089 ms |
コンパイル使用メモリ | 179,840 KB |
実行使用メモリ | 25,344 KB |
最終ジャッジ日時 | 2024-10-15 13:33:52 |
合計ジャッジ時間 | 10,890 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,760 KB |
testcase_01 | AC | 84 ms
6,144 KB |
testcase_02 | AC | 81 ms
6,144 KB |
testcase_03 | AC | 76 ms
6,144 KB |
testcase_04 | AC | 87 ms
6,144 KB |
testcase_05 | AC | 92 ms
6,144 KB |
testcase_06 | TLE | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
ソースコード
#include <bits/stdc++.h> #define _for(i, a, b) for (int i = (a); i <= (b); i ++ ) #define ll long long using namespace std; const int N = 1e5 + 5, P = 998244353; int sub, n, q, dfn_cnt, a[N], sz[N], dep[N], son[N], fa[N], dfn[N], rk[N], top[N]; vector<int> G[N]; inline void Mul(ll & x, ll y) { (x *= y % P) %= P; } inline void Add(ll & x, ll y) { (x += y % P) %= P; } struct Seg_Tree { #define lc p << 1 #define rc p << 1 | 1 #define mid ((tr[p].l + tr[p].r) >> 1) struct Tree { int l, r; ll mul, add, sum; } tr[N << 2]; inline int len(int p) { return tr[p].r - tr[p].l + 1; } inline void push_tag_mul(int p, ll k) { Mul(tr[p].mul, k), Mul(tr[p].add, k), Mul(tr[p].sum, k); } inline void push_tag_add(int p, ll k) { Add(tr[p].add, k), Add(tr[p].sum, 1ll * len(p) * k); } inline void push_up(int p) { tr[p].sum = tr[lc].sum + tr[rc].sum; } inline void push_down(int p) { if (tr[p].mul ^ 1) push_tag_mul(lc, tr[p].mul), push_tag_mul(rc, tr[p].mul), tr[p].mul = 1; if (tr[p].add) push_tag_add(lc, tr[p].add), push_tag_add(rc, tr[p].add), tr[p].add = 0; } void build(int p, int l, int r) { tr[p].l = l, tr[p].r = r, tr[p].add = 0, tr[p].mul = 1; if (l == r) { tr[p].sum = a[rk[l]]; return ; } build(lc, l, mid), build(rc, mid + 1, r), push_up(p); } void update(int p, int l, int r, ll k, ll b) { if (l <= tr[p].l && tr[p].r <= r) { push_tag_mul(p, k), push_tag_add(p, b); return ; } push_down(p); if (l <= mid) update(lc, l, r, k, b); if (r > mid) update(rc, l, r, k, b); push_up(p); } ll query(int p, int x) { if (len(p) == 1) return tr[p].sum; push_down(p); return query(x <= mid ? lc : rc, x); } } T; void dfs1(int u) { sz[u] = 1, son[u] = - 1; for (int v : G[u]) if (v ^ fa[u]) { fa[v] = u, dep[v] = dep[u] + 1, dfs1(v), sz[u] += sz[v]; if (son[u] == - 1 || sz[son[u]] < sz[v]) son[u] = v; } } void dfs2(int u, int Top) { top[u] = Top, rk[dfn[u] = ++ dfn_cnt] = u; if (son[u] == - 1) return ; dfs2(son[u], Top); for (int v : G[u]) if (v ^ fa[u] && v ^ son[u]) dfs2(v, v); } inline int lca(int u, int v) { int U = top[u], V = top[v]; while (U ^ V) { if (dep[U] >= dep[V]) u = fa[U]; else v = fa[V]; U = top[u], V = top[v]; } return dep[u] < dep[v] ? u : v; } inline int dist(int u, int v) { return dep[u] + dep[v] - (dep[lca(u, v)] << 1); } inline void update_path(int u, int v, ll k, ll b) { int U = top[u], V = top[v]; while (U ^ V) { if (dep[U] >= dep[V]) T.update(1, dfn[U], dfn[u], k, b), u = fa[U]; else T.update(1, dfn[V], dfn[v], k, b), v = fa[V]; U = top[u], V = top[v]; } T.update(1, min(dfn[u], dfn[v]), max(dfn[u], dfn[v]), k, b); } inline void update_subtree(int u, ll k, ll b) { T.update(1, dfn[u], dfn[u] + sz[u] - 1, k, b); } inline void update_dist(int u, int r, ll k, ll b) { if (sub == 3 || sub == 5) { T.update(1, dfn[u], dfn[u], k, b); for (int v : G[u]) T.update(1, dfn[v], dfn[v], k, b); } else { _for (i, 1, n) if (dist(i, u) <= r) T.update(1, dfn[i], dfn[i], k, b); } } int main() { ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> q; int op, u, v, r, k, b; _for (i, 2, n) cin >> u >> v, G[u].push_back(v), G[v].push_back(u); _for (i, 1, n) cin >> a[i]; dfs1(1), dfs2(1, 1), T.build(1, 1, n); while (q -- ) { cin >> op >> u; if (op == 1) cout << T.query(1, dfn[u]) << "\n"; else if (op == 2) cin >> r >> k >> b, update_dist(u, r, k, b); else if (op == 3) cin >> k >> b, update_subtree(u, k, b); } return 0; }