90分求调 马蜂良好

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 5e5 + 5;
const int inf = 1e18;

int n, ans, q;
int cur[Maxn], L[Maxn], R[Maxn];
vector<int> ansl, ansr;

struct node{
    int ndv;
    bool op;
}nd[Maxn];

struct edge{
    int to, nxt, l, r;
}e[Maxn << 1];
int tot = -1, head[Maxn];
void add(int u, int v, int l, int r){
    e[++ tot].to = v;
    e[tot].nxt = head[u];
    e[tot].l = l, e[tot].r = r;
    head[u] = tot;
}

int upd(int x, int y, bool op){
    return (op ? x + y : x - y);
}

int Max(int a, int b){
    return a > b ? a : b;
}

int Min(int a, int b){
    return a < b ? a : b;
}

void dfs(int u, int sum, int l, int r){
    cur[u] = sum; L[u] = l; R[u] = r;
    if(L[u] <= R[u]){
        ansl.push_back(L[u]);
        ansr.push_back(R[u]);
    }

    for(int i = head[u]; ~i; i = e[i].nxt){
        int v = e[i].to;

        int now_l = e[i].l - cur[u], now_r = e[i].r - cur[u];
        if(now_l > now_r) continue;

        int newl = Max(now_l, l);
        int newr = Min(now_r, r);
        int newsum = upd(sum, nd[v].ndv, nd[v].op);
        dfs(v, newsum, newl, newr);
    }
}

signed main(){
	//freopen("C:\\Users\\UserX\\Desktop\\calc\\calc2.in", "r", stdin);
    memset(head, -1, sizeof(head));
    cin >> n >> q;
    for(int i = 2; i <= n; i ++){
        int p, l, r;
        cin >> p >> l >> r;
        add(p, i, l, r);
    }

    for(int i = 1; i <= n; i ++){
        char x; cin >> x;
        if(x == '+') nd[i].op = 1;
        else nd[i].op = 0;
        cin >> nd[i].ndv;
    }

    dfs(1, (nd[1].op ? nd[1].ndv : -nd[1].ndv), -inf, inf);

    sort(ansl.begin(), ansl.end());
    sort(ansr.begin(), ansr.end());

    while(q --){
        int x; cin >> x;
        int cntl = upper_bound(ansl.begin(), ansl.end(), x) - ansl.begin();
        int cntr = lower_bound(ansr.begin(), ansr.end(), x) - ansr.begin();
        cout << cntl - cntr << '\n';
    }

    return 0;
}