Untitled
unknown
plain_text
a year ago
4.0 kB
22
Indexable
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define int long long #define fi first #define se second #define pii pair<int, int> #define pb push_back #define vi vector<int> #define bit(i, x) ((x >> i) & 1) #define ALL(x) x.begin(), x.end() #define REP(i, n) for (int i = 1; i <= n; ++i) #define FOR(i, a, b) for (int i = a; i <= b; ++i) #define FORD(i, a, b) for (int i = a; i >= b; --i) #define Random(lf, rt) (lf + rand() % (rt - lf + 1)) #define Task "tchain" using namespace std; const int maxn = 1e5 + 7, N = 1e9 + 7, mod = 1e9 + 7; void ADD(int &x, int y) { x += y; if (x >= mod) x -= mod; if (x < 0) x += mod; } void MAXIMIZE(int &x, int y) { x = max(x, y); } void MINIMIZE(int &x, int y) { x = min(x, y); } struct Data { int l, r; } lrChain[maxn]; int n, q, curCnt, nChains, rootChange; int h[maxn], cnt[maxn], inChain[maxn]; vi adj[maxn]; //calc depth and split into chains void Dfs(int u, int par) { h[u] = h[par] + 1; if (h[u] == 1) { lrChain[nChains].r = curCnt; ++ nChains; lrChain[nChains].l = curCnt + 1; } if (u != 1) { cnt[u] = ++ curCnt; inChain[u] = nChains; } // cerr << u << " " << nChains << " " << h[u] << " " << cnt[u] << " " << inChain[u] << "\n"; for (int v : adj[u]) { if (v == par) continue; Dfs(v, u); } } //tree[0] is global, tree[1] is local int Tree[2][maxn * 4]; void Update(int id, int node, int l, int r, int u, int v, int val) { if (v < l || r < u) return; if (u <= l && r <= v) { Tree[id][node] += val; return; } int mid = (l + r) / 2; Update(id, node * 2, l, mid, u, v, val); Update(id, node * 2 + 1, mid + 1, r, u, v, val); } int Get(int id, int node, int l, int r, int u) { if (u < l || r < u) return 0; if (l == r) return Tree[id][node]; int mid = (l + r) / 2; int t1 = Get(id, node * 2, l, mid, u); int t2 = Get(id, node * 2 + 1, mid + 1, r, u); return Tree[id][node] + t1 + t2; } int RESULT(int v) { if (v == 1) return rootChange; int addG = Get(0, 1, 1, n, cnt[v] - lrChain[inChain[v]].l + 1); int addL = Get(1, 1, 1, n, cnt[v]); return addG + addL; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(Task".inp", "r")) { freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } //input tree cin >> n >> q; REP(i, n - 1) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } h[0] = -1; Dfs(1, 0); lrChain[nChains].r = curCnt; //input query REP(i, q) { int type; cin >> type; if (type == 0) { int v, x, d; cin >> v >> x >> d; if (v == 1) { rootChange += x; Update(0, 1, 1, n, 1, d, x); } else { int curChain = inChain[v]; int L = lrChain[curChain].l; int R = lrChain[curChain].r; if (h[v] >= d) { if (h[v] == d) rootChange += x; int l = max(L, cnt[v] - d); int r = min(R, cnt[v] + d); Update(1, 1, 1, n, l, r, x); } else { rootChange += x; int len = d - h[v]; Update(0, 1, 1, n, 1, len, x); Update(1, 1, 1, n, L, min(R, L + len - 1), -x); int r = min(R, cnt[v] + d); Update(1, 1, 1, n, L, r, x); } } } else { int v; cin >> v; cout << RESULT(v) << "\n"; } } // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; return 0; }
Editor is loading...
Leave a Comment