85pts悬关求调

#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline void write(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 ^ 48);
}
#define endl '\n'
const int N = 7e6 + 2, M = 5e5 + 2;
int n, q;
ll lsh[N], cc, que[N];
struct node {
    char op;
    ll num, now;
    ll lnow, rnow;
}s[M];
int h[M], idx;
struct Edge {
    int to, next;
    ll l, r;
}edge[M];
struct Node {
    int ls, rs;
    __int128 cnt, tag;
}tr[N];
int tot;

void add(int x, int y, ll l, ll r) {
    edge[++ idx].to = y;
    edge[idx].next = h[x];
    edge[idx].l = l, edge[idx].r = r;
    h[x] = idx;
}
void calc(int x, int fa, ll l, ll r) {
    ll d = s[fa].now;
    if (d > 0) {
        if (l < -1e18 + d) l = -1e18;
        else l -= d;
        if (r < -1e18 + d) r = -1e18;
        else r -= d;
    } else {
        if (l > 1e18 + d) l = 1e18;
        else l -= d;
        if (r > 1e18 + d) r = 1e18;
        else r -= d;
    }    
    if (r < s[fa].lnow || l > s[fa].rnow) s[x].lnow = 1e18, s[x].rnow = -1e18;
    else s[x].lnow = max(l, s[fa].lnow), s[x].rnow = min(r, s[fa].rnow);
}
queue<pair<int, ll>> qq;
void dfs() {
    qq.push({1, 0});
    while (qq.size()) {
        auto t = qq.front(); qq.pop();
        int x = t.first;
        ll dd = t.second;
        if (s[x].op == '+') dd += s[x].num;
        else dd -= s[x].num;
        s[x].now = dd;
        for (int i = h[x]; i; i = edge[i].next) {
            int to = edge[i].to;
            qq.push({to, dd});
        }
    }
}
void dfs2() {
    qq.push({1, 0});
    while (qq.size()) {
        auto t = qq.front(); qq.pop();
        int x = t.first;
        if (s[x].lnow > s[x].rnow) return ;
        for (int i = h[x]; i; i = edge[i].next) {
            int to = edge[i].to;
            calc(to, x, edge[i].l, edge[i].r);
            qq.push({to, 0});
        }
    }
}
int New() {
    tot ++;
    tr[tot].ls = tr[tot].rs = 0;
    tr[tot].cnt = 0;
    return tot;
}
void Pushup(int x) {
    tr[x].cnt = tr[tr[x].ls].cnt + tr[tr[x].rs].cnt;
}
void Update(int x, __int128 v, __int128 l, __int128 r) {
    tr[x].cnt += v * (r - l + 1);
    tr[x].tag += v;
}
void Pushdown(int x, ll l, ll r) {
    if (tr[x].tag) {
        ll mid = (l + r) >> 1;
        if (!tr[x].ls) tr[x].ls = New();
        Update(tr[x].ls, tr[x].tag, l, mid);
        if (!tr[x].rs) tr[x].rs = New();
        Update(tr[x].rs, tr[x].tag, mid + 1, r);
        tr[x].tag = 0;
    }
}
void Modify(int x, ll l, ll r, ll ql, ll qr) {
    if (ql > qr) return ;
    if (l >= ql && r <= qr) {
        Update(x, 1, l, r);
        return ;
    }
    Pushdown(x, l, r);
    ll mid = (l + r) >> 1;
    if (ql <= mid) {
        if (!tr[x].ls) tr[x].ls = New();
        Modify(tr[x].ls, l, mid, ql, qr);
    }
    if (mid < qr) {
        if (!tr[x].rs) tr[x].rs = New();
        Modify(tr[x].rs, mid + 1, r, ql, qr);
    }
    Pushup(x);
}
__int128 ask(int x, ll l, ll r, ll v) {
    if (l == r) return tr[x].cnt;
    Pushdown(x, l, r);
    ll mid = (l + r) >> 1;
    if (v <= mid) {
        if (!tr[x].ls) return 0;
        return ask(tr[x].ls, l, mid, v);
    } else {
        if (!tr[x].rs) return 0;
        return ask(tr[x].rs, mid + 1, r, v);
    }
}
void discrete() {
    sort(lsh + 1, lsh + cc + 1);
    cc = unique(lsh + 1, lsh + cc + 1) - (lsh + 1);
}
int find(ll x) {
    return lower_bound(lsh + 1, lsh + cc + 1, x) - lsh;
}
int main() {
    // freopen("calc4.in", "r", stdin); freopen("test.out", "w", stdout);
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i < n; i ++) {
        int p;
        ll l, r;
        cin >> p >> l >> r;
        add(p, i + 1, l, r);
    }
    for (int i = 1; i <= n; i ++) cin >> s[i].op >> s[i].num;
    s[1].lnow = -1e18, s[1].rnow = 1e18;
    for (int i = 2; i <= n; i ++) s[i].lnow = 1e18, s[i].rnow = -1e18;
    dfs(); dfs2(); New();
    for (int i = 1; i <= n; i ++) {
        lsh[++ cc] = s[i].lnow;
        lsh[++ cc] = s[i].rnow;
    }
    for (int i = 1; i <= q; i ++) {
        cin >> que[i];
        lsh[++ cc] = que[i];
    }
    discrete();
    for (int i = 1; i <= n; i ++) {
        Modify(1, 1, cc, find(s[i].lnow), find(s[i].rnow));
        if (i < 2000) cerr << find(s[i].lnow) << " " << find(s[i].rnow) << endl;
    }
    
    for (int i = 1; i <= q; i ++) {
        write(ask(1, 1, cc, find(que[i])));
        putchar('\n');
    }
    return 0;
}