решение A 800ms

#include <bits/stdc++.h>
using namespace std;
#define int uint32_t
#pragma GCC optimize("Ofast,unroll-loops")
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n-1; i += 1) {
        int u, v;
        cin >> u >> v;
        u -= 1, v -= 1;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> tin1(n), tout1(n), tin2(n), tout2(n);
    int t1 = 0;
    vector<int> d(n);
    auto dfs1 = [&] (auto f, int u, int p) -> void {
        tin1[u] = t1++;
        for (const auto &x : adj[u]) {
            if (x != p) {
                d[x] = d[u]+1;
                f(f, x, u);
            }
        }
        tout1[u] = t1-1;
    };
    int t2 = 0;
    auto dfs2 = [&] (auto f, int u, int p) -> void {
        tin2[u] = t2;
        for (const auto &x : adj[u]) {
            if (x != p) {
                f(f, x, u);
            }
        }
        tout2[u] = t2++;
    };
    dfs1(dfs1, 0, 0);
    dfs2(dfs2, 0, 0);
    struct Node {
        int val=0;
        int lz=0;
    };
    auto push = [&] (int u, int tl, int tr, vector<Node>& ST) -> void {
        int tm = (tl + tr) >> 1;
        int szl = tm-tl+1;
        int szr = tr-(tm+1)+1;
        ST[2*u+1].lz += ST[u].lz;
        ST[2*u+1].val += ST[u].lz*szl;
        ST[2*u+2].lz += ST[u].lz;
        ST[2*u+2].val += ST[u].lz*szr;
        ST[u].lz = 0;
    };
    auto inc = [&] (auto f, int u, int tl, int tr, int l, int r, int x, vector<Node>& ST) -> void {
        if (tl == l && tr == r) {
            ST[u].val += x*(tr-tl+1);
            ST[u].lz += x;
            return;
        }
        int tm = (tl + tr) >> 1;
        push(u, tl, tr, ST);
        if (l <= tm) {
            f(f, 2*u+1, tl, tm, l, min(r, tm), x, ST);
        }
        if (r >= tm+1) {
            f(f, 2*u+2, tm+1, tr, max(tm+1, l), r, x, ST);
        }
        ST[u].val = ST[2*u+1].val + ST[2*u+2].val;
    };
    auto gt = [&] (auto f, int u, int tl, int tr, int l, int r, vector<Node>& ST) -> int {
        if (tl == l && tr == r) {
            return ST[u].val;
        }
        int tm = (tl + tr) >> 1;
        push(u, tl, tr, ST);
        int ret = 0;
        if (l <= tm) {
            ret += f(f, 2*u+1, tl, tm, l, min(r, tm), ST);
        }
        if (r >= tm+1) {
            ret += f(f, 2*u+2, tm+1, tr, max(tm+1, l), r, ST);
        }
        return ret;
    };
    vector<Node> vals(4*n+10), cancelled(4*n+10);
    auto inc_on_path_to_root = [&] (int u, int x) -> void {
        inc(inc, 0, 0, n-1, 0, tout1[u], x, vals);
        if (tout2[u] >= 1) {
            inc(inc, 0, 0, n-1, 0, tout2[u]-1, x, cancelled);
        }
    };
    auto gt_subtree = [&] (int u) -> int {
        return gt(gt, 0, 0, n-1, tin1[u], tout1[u], vals)-gt(gt, 0, 0, n-1, tin2[u], tout2[u], cancelled);
    };
    int ans = 0;
    for (int ii = 0; ii < q; ii += 1) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int u;
            cin >> u;
            u -= 1;
            inc_on_path_to_root(u, 1);
        }
        if (tp == 2) {
            int u;
            cin >> u;
            u -= 1;
            ans += gt_subtree(u);
        }
        if (ii % 100 == 99) {
            cout << ans << endl;
            ans = 0;
        }
    }
}