题意
题解
考虑把一个玩家的路径 ((x, y)) 拆成两条，一条是 (x) 到 (lca) （ (x, y) 最近公共祖先） 的路径，另一条是 (lca) 到 (y) 的路径。（对于 (x, y) 是 (lca) 的情况需要特殊考虑一下就行了）
这个求 (lca) 的过程用倍增实现就行了。
假设令到达时间为 (at) 。
不难发现，在树上向上的路径满足 (dep_u + at_u=d_1) （深度+到达时间） 是个定值。这个可以这样考虑，向上走 到达时间 (+1) ，且深度会 (-1) ，所以不会变。
同理可得，向下走的路径满足 (dep_u - at_u=d_2) （深度-到达时间） 是个定值。
我们考虑对于一条路径，差分表示在树上，也就是 (x o y) 这条路径，我们在 (x) 处加入， (y) 处除去。
然后考虑每次我们线段树合并两个子树维护关于 (d_1) 以及 (d_2) 出现的次数。
然后对于一个点 (u) 要查询的就是 (dep_u + w_u = d_1') 的值，以及 (dep_u - w_u = d_2') 的值。
时间复杂度是 (O(n log n)) 的，其实跑得挺快的？
具体看代码实现吧qwq。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * fh;
}
void File() {
#ifdef zjp_shadow
freopen ("2359.in", "r", stdin);
freopen ("2359.out", "w", stdout);
#endif
}
const int N = 3e5 + 1e3, Maxn = N * 40;
#define lson ls[o], l, mid
#define rson rs[o], mid + 1, r
struct Segment_Tree {
int ls[Maxn], rs[Maxn], sumv[Maxn], Size;
Segment_Tree() { Size = 0; }
void Update(int &o, int l, int r, int up, int uv) {
if (!o) o = ++ Size;
if (l == r) { sumv[o] += uv; return ; }
int mid = (l + r) >> 1;
if (up <= mid) Update(lson, up, uv); else Update(rson, up, uv);
}
int Query(int o, int l, int r, int qp) {
if (l == r) return sumv[o];
int mid = (l + r) >> 1;
return qp <= mid ? Query(lson, qp) : Query(rson, qp);
}
int Merge(int x, int y, int l, int r) {
if (!x || !y) return x | y;
if (l == r) { sumv[x] += sumv[y]; return x; }
int mid = (l + r) >> 1;
ls[x] = Merge(ls[x], ls[y], l, mid);
rs[x] = Merge(rs[x], rs[y], mid + 1, r);
return x;
}
} TU, TD;
int to[N][23], dep[N], Log2[N]; vector<int> G[N];
void Dfs_Init(int u, int fa = 0) {
to[u][0] = fa; dep[u] = dep[fa] + 1;
for (int v : G[u]) if (v != fa) Dfs_Init(v, u);
}
int tmp;
inline int Get_Lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int gap = dep[x] - dep[y];
For (i, 0, Log2[gap] + 1)
if ((gap >> i) & 1) x = to[x][i];
if (x == y) return x;
Fordown (i, Log2[dep[x]], 0)
if (to[x][i] != to[y][i]) x = to[x][i], y = to[y][i]; tmp = y;
return to[x][0];
}
int n, m, W[N], ans[N];
vector<int> TagU[N], TagD[N], DelU[N], DelD[N];
int rtU[N], rtD[N];
void Dfs(int u, int fa = 0) {
for (int v : G[u]) if (v ^ fa) {
Dfs(v, u);
rtU[u] = TU.Merge(rtU[u], rtU[v], -n, n * 2);
rtD[u] = TD.Merge(rtD[u], rtD[v], -n, n * 2);
}
for (int pos : TagU[u]) TU.Update(rtU[u], -n, n * 2, pos, 1);
for (int pos : TagD[u]) TD.Update(rtD[u], -n, n * 2, pos, 1);
ans[u] = TU.Query(rtU[u], -n, n * 2, W[u] + dep[u]) +
TD.Query(rtD[u], -n, n * 2, W[u] - dep[u]) ;
for (int pos : DelU[u]) TU.Update(rtU[u], -n, n * 2, pos, -1);
for (int pos : DelD[u]) TD.Update(rtD[u], -n, n * 2, pos, -1);
}
int main () {
File();
n = read(); m = read();
For (i, 1, n - 1) { int u = read(), v = read(); G[u].push_back(v); G[v].push_back(u); }
Dfs_Init(1);
For (i, 2, n)
Log2[i] = Log2[i >> 1] + 1;
For (j, 1, Log2[n]) For (i, 1, n)
to[i][j] = to[to[i][j - 1]][j - 1];
For (i, 1, n)
W[i] = read();
For (i, 1, m) {
int x = read(), y = read(), Lca = Get_Lca(x, y);
int d1 = dep[x], d2 = - dep[x];
if (Lca == y) { TagU[x].push_back(d1); DelU[y].push_back(d1); continue ; }
if (Lca == x) { TagD[y].push_back(d2); DelD[x].push_back(d2); continue ; }
d2 = (dep[x] - dep[Lca] + 1) - dep[tmp];
TagU[x].push_back(d1); DelU[Lca].push_back(d1);
TagD[y].push_back(d2); DelD[tmp].push_back(d2);
}
Dfs(1);
For (i, 1, n)
printf ("%d%c", ans[i], i == iend ? '
' : ' ');
return 0;
}