100589A.cpp

#include <bits/stdc++.h>
#define NMAX 100006
#define TMAX 400030
using namespace std;

typedef long long ll;

ll n, m;
ll nodes[NMAX], par[NMAX], depth[NMAX];
ll height[NMAX];
vector<ll> adj[NMAX];
ll seg[TMAX];

ll get_mid(ll x, ll y) {
    return x + (y - x) / 2;
}

void update(ll node, ll start, ll end, ll x, ll val) {
    if(start > end || start > x || end < x)
        return ;
    if(start == end) {
        seg[node] += val;
        return ;
    }
    ll mid = get_mid(start, end);
    if(x <= mid)
        update(2*node, start, mid, x, val);
    else
        update(2*node+1, mid+1, end, x, val);
    seg[node] = seg[2*node] + seg[2*node+1];
}

ll query(ll node, ll start, ll end, ll left, ll right) {
    if(start > end || start > right || end < left)
        return 0;
    if(left <= start && end <= right)
        return seg[node];
    ll mid = get_mid(start, end);
    return query(2*node, start, mid, left, right) +
            query(2*node+1, mid+1, end, left, right);
}

void bfs(ll u) {
    queue< pair<ll,ll> > qu;
    qu.push(make_pair(u, 0));
    while(!qu.empty()) {
        ll v = qu.front().first;
        ll ht = qu.front().second;
        qu.pop();
        nodes[ht] = adj[par[v]].size();
        depth[v] = ht;
        for(ll w : adj[v])
            qu.push(make_pair(w, ht+1));
    }
}

ll dfs(ll u) {
    if(adj[u].size() == 0) {
        height[u] = 0;
        return 0;
    }
    for(ll v : adj[u])
        height[u] = max(height[u], 1LL + dfs(v));
    return height[u];
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(ll i = 0; i < n-1; i++) {
        ll u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        par[v] = u;
    }
    par[1] = 0;
    adj[0].push_back(1);
    memset(seg, 0, sizeof(seg));
    memset(nodes, 0, sizeof(nodes));
    bfs(1);
    dfs(1);
    while(m--) {
        ll x, y;
        cin >> x >> y;
        if(x == 1) {
            ll z;
            cin >> z;
            update(1, 0, n-1, y, nodes[y]*z);
        }
        else
            cout << query(1, 0, n-1, depth[y], depth[y]) / nodes[depth[y]] +
                    query(1, 0, n-1, depth[y]+1, depth[y]+height[y]) << endl;
    }
    return 0;
}