虽然好像看起来不难，但是就是想不到啊
部分分感觉可以拿\(60pts\)，但还没打代码验证完，分析暂时不放上来
看一看\(NOIP2016\)年鉴，发现其实正解就是许多档部分分的想法的整合，这启示我们在拿到一道难题的时候，如果对正解暂时没有什么思路，可以考虑尽可能多的想部分分怎么打，一是你反正还是要对拍，二是部分分的做法可能内嵌\(std\)
从\(\forall s_i = 1\)的部分分入手，发现\(\forall s_i = 1\)时其实就是对于每一条路径头尾差分一下，然后对于每个\(dep_i = w_i\)的点统计一下它的子树和
那么正解呢
考虑把每一条路径拆成上行和下行两条路径，感觉和上面的部分分有共通之处，能不能继续考虑差分呢
答案是可以的
先考虑上行，还是在起点打\(+1\)标记，但是这样还不行，万一在\(LCA\)的地方拐下去了呢，所以还要在\(LCA\)的地方减一下
考虑这样的话一个点要满足什么条件
设起点为\(st\)，那么有\(dep_st - w_i = dep_i\)时，从起点出发，跑过这个点的时候可以被观测到
移项一下 \(dep_st = dep_i + w_i\)，即在\(dep_st\)这一层上打一下标记，查询时查询\(dep_i + w_i\)这层的子树和
下行类似，在终点\(ed\)处打标记，柿子列出来发现是\(Len - (dep_ed - dep_i) = w_i\)，其中\(Len\)指跑步的路径长度
移项一下是\(Len - dep_ed = w_i - dep_i\)，然后同上打一下标记，注意为了保证\(LCA\)处的贡献可以正常统计，上行和下行的\(-1\)标记有一个要打在\(fa[LCA]\)上
对于每一层子树和的统计，我们对着每一个\(dep\)开一棵线段树，然后动态开点一下，查询子树和就是\(dfs\)序上连续一段
#include<bits/stdc++.h>
#define N (600000 + 10)
using namespace std;
inline int read() {
int cnt = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + (c ^ 48); c = getchar();}
return cnt * f;
}
int n, m, u, v, w[N], tot;
struct node {int s, t, l;} a[N];
int nxt[N], first[N], to[N];
void add(int x, int y) {nxt[++tot] = first[x], first[x] = tot, to[tot] = y;}
int fa[N], siz[N], dep[N], son[N], top[N], num[N], idx;
void dfs1(int cur, int father) {
fa[cur] = father, dep[cur] = dep[father] + 1, siz[cur] = 1;
for (register int i = first[cur]; i; i = nxt[i]) {
int v = to[i];
if (v == father) continue;
dfs1(v, cur);
siz[cur] += siz[v];
if (siz[son[cur]] < siz[v]) son[cur] = v;
}
}
void dfs2(int cur, int tp) {
top[cur] = tp, num[cur] = ++idx;
if (son[cur]) dfs2(son[cur], tp);
for (register int i = first[cur]; i; i = nxt[i]) {
int v = to[i];
if (num[v]) continue;
dfs2(v, v);
}
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
} return dep[u] < dep[v] ? u : v;
}
int ans[N];
int now, rt[N], ls[N * 20], rs[N * 20], val[N * 20];
void modify(int &x, int l, int r, int pos, int v) {
if (!x) x = ++now; val[x] += v; if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid) modify(ls[x], l, mid, pos, v);
else modify(rs[x], mid + 1, r, pos, v);
}
int query(int x, int l, int r, int L, int R) {
if (!x) return 0; if (L <= l && R >= r) return val[x];
int mid = (l + r) >> 1, ans = 0;
if (L <= mid) ans += query(ls[x], l, mid, L, R);
if (R > mid) ans += query(rs[x], mid + 1, r, L, R);
return ans;
}
void clear() {for (register int i = 1; i <= now; ++i) ls[i] = rs[i] = val[i] = 0; memset(rt, 0, sizeof rt); now = 0;}
int main() {
n = read(), m = read();
for (register int i = 1; i < n; ++i) {
u = read(), v = read();
add(u, v), add(v, u);
}
dfs1(1, 0), dfs2(1, 1);
for (register int i = 1; i <= n; ++i) w[i] = read();
for (register int i = 1; i <= m; ++i) a[i].s = read(), a[i].t = read(), a[i].l = lca(a[i].s, a[i].t);
/*-----------go up------------*/
for (register int i = 1; i <= m; ++i) {
modify(rt[dep[a[i].s]], 1, n, num[a[i].s], 1);
if (fa[a[i].l]) modify(rt[dep[a[i].s]], 1, n, num[fa[a[i].l]], -1);
}
for (register int i = 1; i <= n; ++i) ans[i] = query(rt[dep[i] + w[i]], 1, n, num[i], num[i] + siz[i] - 1);
/*----------go up-------------*/
clear();
/*----------go down -----------*/
for (register int i = 1; i <= m; ++i) {
int Len = dep[a[i].t] + dep[a[i].s] - 2 * dep[a[i].l];
int cur = Len - dep[a[i].t] + n;
modify(rt[cur], 1, n, num[a[i].t], 1);
modify(rt[cur], 1, n, num[a[i].l], -1);
}
for (register int i = 1; i <= n; ++i) ans[i] += query(rt[w[i] - dep[i] + n], 1, n, num[i], num[i] + siz[i] - 1);
for (register int i = 1; i <= n; ++i) printf("%d ", ans[i]);
return 0;
}原文：https://www.cnblogs.com/kma093/p/11809138.html