Untitled
unknown
plain_text
a year ago
4.0 kB
27
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