其实是个套路题？ 近三年 NOIP 数据结构题 \(\frac23\) 达成 \(\surd\)
考虑一位从 \(u\) 到 \(v\) 的玩家，令 \(lca = \text{LCA}(u,v)\)。
再设 \(\text{dep}_u\) 表示 \(u\) 的深度，\(\text{fa}_u\) 表示 \(u\) 的父亲。
那么考虑一个在 \((u,lca)\) 路径上的点 \(p\)，若它能观察到 \(p\)，则一定有 \(\text{dep}_u-\text{dep}_p=W_p\)。
移项得 \(\text{dep}_u=W_p+\text{dep}_p\)。
再考虑一个在 \((lca,v)\) 路径上的点 \(p\)，若它能观察到 \(p\)，则有 \(\text{dep}_u+\text{dep}_p-2\text{dep}_{lca}=W_p\)。
移项得 \(\text{dep}_u-2\text{dep}_{lca}=W_p-\text{dep}_p\)。
则，对于任意点 \(p\) 的观察员，若其可以观察到一个从 \(u\) 到 \(v\) 的玩家，则一定满足： 1. 其在 \((u,v)\) 路径上。 2. \(\text{dep}_u=W_p+\text{dep}_p\) 或 \(\text{dep}_u-2\text{dep}_{lca}=W_p-\text{dep}_p\)。
则对于每个点的贡献，可以用树上差分来维护，注意 \(lca\) 处的细节判断。
线段树合并即可（虽然其实不需要）。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
using namespace std;
const int N = 299998;
int n,m;
int a[N + 5];
int to[N * 2 + 5],pre[N * 2 + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5];
int q[N + 5],head,tail;
void bfs()
{
dep[q[++tail] = 1] = 1;
for(register int p;head < tail;)
{
++sz[p = q[++head]];
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
fa[to[i]] = p,dep[to[i]] = dep[p] + 1,q[++tail] = to[i];
}
for(register int i = n;i;--i)
{
sz[fa[q[i]]] += sz[q[i]];
if(!son[fa[q[i]]] || sz[q[i]] > sz[son[fa[q[i]]]])
son[fa[q[i]]] = q[i];
}
for(register int i = 1;i <= n;++i)
top[q[i]] = son[fa[q[i]]] == q[i] ? top[fa[q[i]]] : q[i];
}
inline int getlca(int x,int y)
{
while(top[x] ^ top[y])
dep[top[x]] > dep[top[y]] ? (x = fa[top[x]]) : (y = fa[top[y]]);
return dep[x] < dep[y] ? x : y;
}
struct node
{
int sum;
int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5][2];
void insert(int x,int k,int &p,int tl,int tr)
{
static int tot = 0;
!p && (p = ++tot),seg[p].sum += k;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
}
int query(int x,int p,int tl,int tr)
{
if(!p || tl == tr)
return seg[p].sum;
int mid = tl + tr >> 1;
return x <= mid ? query(x,seg[p].ls,tl,mid) : query(x,seg[p].rs,mid + 1,tr);
}
int merge(int x,int y)
{
if(!x || !y)
return x | y;
seg[x].sum += seg[y].sum;
seg[x].ls = merge(seg[x].ls,seg[y].ls),seg[x].rs = merge(seg[x].rs,seg[y].rs);
return x;
}
int ans[N + 5];
int main()
{
scanf("%d%d",&n,&m);
int u,v;
for(register int i = 1;i < n;++i)
scanf("%d%d",&u,&v),add(u,v),add(v,u);
bfs();
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
for(register int lca;m;--m)
{
scanf("%d%d",&u,&v),lca = getlca(u,v);
insert(dep[u],1,rt[u][0],0,2 * n),insert(dep[u],-1,rt[fa[lca]][0],0,2 * n);
insert(dep[u] - 2 * dep[lca],1,rt[v][1],-n,n),insert(dep[u] - 2 * dep[lca],-1,rt[lca][1],-n,n);
}
for(register int i = n;i;--i)
ans[q[i]] = query(dep[q[i]] + a[q[i]],rt[q[i]][0],0,2 * n) + query(a[q[i]] - dep[q[i]],rt[q[i]][1],-n,n),
rt[fa[q[i]]][0] = merge(rt[fa[q[i]]][0],rt[q[i]][0]),
rt[fa[q[i]]][1] = merge(rt[fa[q[i]]][1],rt[q[i]][1]);
for(register int i = 1;i <= n;++i)
printf("%d ",ans[i]);
}