#include #include #include #define ll unsigned int using namespace std; class Seg { private: ll sz; vector vec; vector mulLazy; vector addLazy; void update_Lazy(ll n, ll s, ll e) { if (mulLazy[n] == 1 && addLazy[n] == 0) return; if (s != e) { for (ll subn = n * 2; subn <= n * 2 + 1; subn++) { addLazy[subn] = ((addLazy[subn] * mulLazy[n]) + addLazy[n]); mulLazy[subn] = mulLazy[subn] * mulLazy[n]; } } vec[n] = ((mulLazy[n] * vec[n]) + (e - s + 1) * addLazy[n]); mulLazy[n] = 1; addLazy[n] = 0; return; } void update(ll n, ll s, ll e, ll l, ll r, ll mul, ll add) { update_Lazy(n, s, e); if (r < s || e < l) return; if (l <= s && e <= r) { addLazy[n] = ((addLazy[n] * mul) + add); mulLazy[n] = mulLazy[n] * mul; update_Lazy(n, s, e); return; } ll mid = (s + e) / 2; update(n * 2, s, mid, l, r, mul, add); update(n * 2 + 1, mid + 1, e, l, r, mul, add); vec[n] = (vec[n * 2] + vec[n * 2 + 1]); return; } ll query(ll n, ll s, ll e, ll l, ll r) { update_Lazy(n, s, e); if (r < s || e < l) return 0; if (l <= s && e <= r) return vec[n]; ll mid = (s + e) / 2; return (query(n * 2, s, mid, l, r) + query(n * 2 + 1, mid + 1, e, l, r)); } public: Seg(ll n) { sz = n; vec.resize(sz * 4, 0); mulLazy.resize(sz * 4, 1); addLazy.resize(sz * 4, 0); } void update(ll l, ll r, ll mul, ll add) { return update(1, 1, sz, l, r, mul, add); } ll query(ll l, ll r) { return query(1, 1, sz, l, r); } }; ll par[505050], top[505050], siz[505050], in[505050], dep[505050], out[505050]; ll cnt = 0; vector v[505050]; void dfs1(ll visited) { siz[visited] = 1; for (auto &i : v[visited]) { if (i == par[visited]) continue; dep[i] = dep[visited] + 1; par[i] = visited; dfs1(i); siz[visited] += siz[i]; if (siz[i] > siz[v[visited][0]]) swap(i, v[visited][0]); } } void dfs2(ll visited) { in[visited] = ++cnt; for (auto i : v[visited]) { if (i == par[visited]) continue; top[i] = (i == v[visited][0] ? top[visited] : i); dfs2(i); } out[visited] = cnt; } ll query(Seg &seg, ll u, ll v) { ll ret = 0; while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); ret += seg.query(in[top[u]], in[u]) ; u = par[top[u]]; } if (dep[u] > dep[v]) swap(u, v); ret += seg.query(in[u], in[v]); return ret ; } void update(Seg &seg, ll u, ll v, ll add, ll mul) { while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); seg.update(in[top[u]], in[u], add, mul); u = par[top[u]]; } if (dep[u] > dep[v]) swap(u, v); seg.update(in[u], in[v], add, mul); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n, m; cin >> n >> m; for (ll i = 0; i < n - 1; i++) { ll sub, sub2; cin >> sub >> sub2; v[sub].push_back(sub2); v[sub2].push_back(sub); } top[1] = 1; dfs1(1); dfs2(1); Seg seg(n); for (ll i = 0; i < m; i++) { ll sub, sub2, sub3, sub4; cin >> sub >> sub2; if (sub == 1) { cin >> sub3; seg.update(in[sub2], out[sub2], 1, sub3); } if (sub == 2) { cin >> sub3 >> sub4; update(seg, sub2, sub3, 1, sub4); } if (sub == 3) { cin >> sub3; seg.update(in[sub2], out[sub2], sub3, 0); } if (sub == 4) { cin >> sub3 >> sub4; update(seg, sub2, sub3, sub4, 0); } if (sub == 5) { cout << seg.query(in[sub2], out[sub2]) << '\n'; } if (sub == 6) { cin >> sub3; cout << query(seg, sub2, sub3) << '\n'; } } return 0; }

코드 #1970