D34:

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n, m, head[300100], cnt = 0, dep[300100], rev[300100], tot = 0, sz[300100], res[300100], BIT[300100];

struct Edge{
    int to, next;
    Edge() : to(0), next(0) {}
} edge[600100];

int ae(int u, int v){
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
    return 0;
}

void dfs(int x, int fa){
    rev[x] = ++tot;
    sz[x] = 1;
    for(int i = head[x]; i != -1; i = edge[i].next) {
        if(edge[i].to != fa) {
            dep[edge[i].to] = dep[x] + 1;
            dfs(edge[i].to, x);
            sz[x] += sz[edge[i].to];
        }
    }
}

struct Point{
    int u, v, w;
    Point(int a = 0, int b = 0, int c = 0){
        u = a, v = b, w = c;
    }
    friend bool operator <(const Point &x, const Point &y){
        return x.v < y.v;
    }
} p[300100];

struct Query{
    int x1, x2, y, id;
    Query(int a = 0, int b = 0, int c = 0, int d = 0){
        x1 = a, x2 = b, y = c, id = d;
    }
    friend bool operator <(const Query &x, const Query &y){
        return x.y < y.y;
    }
} q[600100];

int lowbit(int x){
    return x & -x;
}

void add(int x, int val){
    while(x <= n) {
        BIT[x] += val;
        x += lowbit(x);
    }
}

int ask(int x){
    int sum = 0;
    while(x) {
        sum += BIT[x];
        x -= lowbit(x);
    }
    return sum;
}

signed main(){
    scanf("%lld%lld", &n, &m);
    
    // Initialize arrays
    for(int i = 0; i < 300100; i++) {
        head[i] = -1;
        dep[i] = 0;
        rev[i] = 0;
        sz[i] = 0;
        res[i] = 0;
        BIT[i] = 0;
    }
    cnt = 0;
    tot = 0;
    
    for(int i = 0; i < 600100; i++) {
        edge[i].to = 0;
        edge[i].next = 0;
    }
    
    for(int i = 1, x, y; i < n; i++) {
        scanf("%lld%lld", &x, &y);
        ae(x, y);
        ae(y, x);
    }
    
    dfs(1, 0);
    
    for(int i = 1; i <= n; i++) {
        p[i] = Point(rev[i], dep[i], sz[i] - 1);
    }
    
    for(int i = 1; i <= m; i++) {
        int x, y;
        scanf("%lld%lld", &x, &y);
        res[i] += (sz[x] - 1) * min(dep[x], y);
        q[(i << 1) - 1] = Query(rev[x], rev[x] + sz[x] - 1, dep[x], -i);
        q[(i << 1)] = Query(rev[x], rev[x] + sz[x] - 1, dep[x] + y, i);
    }
    
    sort(p + 1, p + n + 1);
    sort(q + 1, q + (m * 2) + 1);
    
    for(int i = 1, j = 1; i <= (m * 2); i++) {
        while(j <= n && p[j].v <= q[i].y) {
            add(p[j].u, p[j].w);
            j++;
        }
        if(q[i].id > 0) {
            res[q[i].id] += ask(q[i].x2) - ask(q[i].x1 - 1);
        } else {
            res[-q[i].id] -= ask(q[i].x2) - ask(q[i].x1 - 1);
        }
    }
    
    for(int i = 1; i <= m; i++) {
        printf("%lld\n", res[i]);
    }
    
    return 0;
}

P3899 [湖南集训] 更为厉害

解法1：线段树合并

视频链接

解法2：可持久化线段树+DFS

视频链接

C67 线段树合并 P3899 [湖南集训] 更为厉害

C64 可持久化线段树+DFS P3899 [湖南集训] 更为厉害