mxqz 线段树合并

WA 6pts，虽然没有新开节点但是我是离线做询问的，所以删掉冗余节点了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>

#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout)
#define v(u) u ? u->v : 0

using namespace std;
using LL = long long;

const int N = 300010;

int n, m;
int h[N], ver[N << 1], ne[N << 1], tot = 1;
LL siz[N];
int depth[N];
struct Query { int id, k; };
vector<Query> q[N];
LL res[N];

struct Node {
    int l, r;
    LL v;
    Node *ls, *rs;
} *tr[N];

inline void add(int u, int v) {
    ver[++tot] = v, ne[tot] = h[u], h[u] = tot;
}

void pushup(Node* &u) {
    u->v = v(u->ls) + v(u->rs);
}

void insert(Node* &u, int l, int r, int x, int val) {
    if (!u) u = new Node(), u->l = l, u->r = r;
    if (l == r) {
        u->v += val;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid) insert(u->ls, l, mid, x, val);
    else insert(u->rs, mid + 1, r, x, val);
    pushup(u);
}

Node* merge(Node* &u, Node* &v) {
    if (!u || !v) return u ? u : v;
    if (u->l == u->r) {
        u->v += v->v;
        delete v;
        return u;
    }
    u->ls = merge(u->ls, v->ls);
    u->rs = merge(u->rs, v->rs);
    pushup(u);
    delete v;
    return u;
}

LL query(Node* &u, int l, int r) {
    if (!u) return 0;
    if (u->l >= l && u->r <= r) return u->v;
    LL res = 0;
    int mid = u->l + u->r >> 1;
    if (l <= mid) res = query(u->ls, l, r);
    if (r > mid) res += query(u->rs, l, r);
    return res;
}

void dfs1(int u, int father) {
    siz[u] = 1, depth[u] = depth[father] + 1;
    for (int i = h[u]; i; i = ne[i]) {
        int v = ver[i];
        if (v == father) continue;
        dfs1(v, u);
        siz[u] += siz[v];
    }
}

void dfs2(int u, int father) {
    insert(tr[u], 1, n, depth[u], siz[u] - 1);
    for (int i = h[u]; i; i = ne[i]) {
        int v = ver[i];
        if (v == father) continue;
        dfs2(v, u);
        tr[u] = merge(tr[u], tr[v]);
    }
    for (auto it : q[u]) res[it.id] = query(tr[u], depth[u] + 1, depth[u] + it.k) + (LL)min(depth[u] - 1, it.k) * (siz[u] - 1);
}

int main() {
    //file("lihai");
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= m; i++) {
        int u, k;
        cin >> u >> k;
        q[u].push_back({i, k});
    }

    dfs1(1, 0);
    dfs2(1, 0);

    for (int i = 1; i <= m; i++)
        cout << res[i] << '\n';
    return 0;
}