結果

問題 No.2340 Triple Tree Query (Easy)
コンテスト
ユーザー vjudge1
提出日時 2024-10-15 13:33:38
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0