Untitled

 avatar
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