Solution
题意
原题链接
感觉题意很难形式化，建议自己读一下。
大概是：给一个定根树，每个点有一个点权，每条边有一个可通过区间，从根开始，带着一个初值向下走，每到一个点把点权加在值上，对初值 \(x\) 的 \(q\) 个取值求可达点数量。
注意：根节点算可达点，根节点的点权也要加上。
分析
首先有一个很自然的思路：对于一个可达点 \(u\)，如果初值是 \(x\)，从根到 \(u\) 的路径点权和是 \(s\)，到达 \(u\) 时的值就是 \(x+s\)。于是对于 \(u\) 向下的边，如果它的可通过区间是 \([l,r]\)，那么可以通过这条边的初值区间就是 \([l-s,r-s]\)。
好的，其实就做完了。我们直接 dfs 一次计算根到所有点的路径点权，并计算可通过区间。注意一下每个点的可达区间应对父亲取交，毕竟要先到父亲才能到它。至于统计答案，我们需要做区间加，单点查，写个差分数组就完……了吗？
注意到 \(x \in [-1 \times 10^{18},1 \times 10^{18}]\)，差分数组完全开不下。但是，我们发现：每个树上的点会做两次差分数组上的操作，所以只有 \(O(n)\) 个差分数组的位是有意义的，那我们只对这些位操作就行了。相当于是：我们“离散化”了差分数组。
具体地，开一个 vector，存 \(x,d\) 表示我需要在差分数组的 \(x\) 位上执行加 \(d\) 操作。查询离线一下，对 \(x\) 排序后扫，就扫完 \(x\) 及之前的求和就行（这好像叫扫描线是吧）。
Tip：注意要扔掉 \(l>r\) 的区间，不然差分数组会错。赛时蒟蒻就是这样调了 30min。
注意下路径点权和会爆 long long，记得开 int128。
Code
#include <iostream>
#include <cctype>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>typedef long long ll;ll fr() {ll x=0,f=1;char c=getchar();while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;
}struct node{ll i;int d;bool operator< (const node &n) const&{return i<n.i;}
};std::vector<node> v;//差分数组的 vectorconst int maxn=5e5+100;struct edge{int v,nxt;ll l,r;
}e[maxn<<1];int head[maxn],tot;void ade(int u,int v,ll l,ll r) {e[++tot]={v,head[u],l,r};head[u]=tot;
}ll a[maxn];void dfs(int u,__int128_t dx,ll fl,ll fr) {dx+=a[u];for(int i = head[u]; i; i=e[i].nxt) {__int128_t l=e[i].l,r=e[i].r;l+=dx,r+=dx;l=std::max((__int128_t)-1e18-100,l),r=std::min((__int128_t)1e18+100,r);//x 的范围只有这么大，多的不用管l=std::max((ll)l,fl),r=std::min((ll)r,fr);if(l>r) continue;v.push_back({(ll)l,1});v.push_back({(ll)r+1,-1});dfs(e[i].v,dx,l,r);}
}struct qry{ll x;int id,ans;
};bool cmp1(qry q1,qry q2) {return q1.x<q2.x;
}bool cmp2(qry q1,qry q2) {return q1.id<q2.id;
}qry Q[maxn<<1];int main() {int n=fr(),q=fr();v.reserve(n<<1);for(int i = 1; i < n; i++) {int p=fr();ll l=fr(),r=fr();ade(p,i+1,l,r);}for(int i = 1; i <= n; i++) a[i]=-fr();dfs(1,0,LLONG_MIN,LLONG_MAX);std::sort(v.begin(),v.end());for(int i = 1; i <= q; i++) Q[i]={fr(),i,0};std::sort(Q+1,Q+1+q,cmp1);int now=0;int p=0;for(int i = 1; i <= q; i++) {ll x=Q[i].x;while(p<v.size()&&v[p].i<=x) {now+=v[p].d;p++;}Q[i].ans=now;}std::sort(Q+1,Q+1+q,cmp2);for(int i = 1; i <= q; i++) printf("%d\n",Q[i].ans+1);return 0;
}
一些闲话
如果觉得有用，点个赞吧！