这道题本来想着等初赛晚再切的....结果到了机房发现大佬们都切了qwq 没办法啊，就...大概看了一下，果然好难啊!QAQ
Code:
1 /*
2 首先我们可以想到对于每个运动员都进行计算，但是复杂度太高了，所以我们转换思想
3 对于每个观测点计算都有谁对它做出了贡献
4 然后对于一条路径(s,t)我们把它拆开分为两部分s -> LCA(s,t) 和 LCA(s,t) -> t
5 然后就会出现两种情况：
6 一：观测点p在 s -> LCA(s,t) 上,那么就是上行,那么满足dep[s]=w[p]+dep[p]的起点s就会对p产生贡献
7 我们用一个桶b1来维护上行产生的贡献值,对于每个观测点直接读取桶中b1[w[p]+dep[p]]的值即可
8 二：观测点在 LCA(s,t) -> t 上,那么就是下行,那么满足dist[s,t]-w[p] = dep[t]-dep[p]移项后就是dist[s,t]-dep[t]=w[p]-dep[p]
9 的终点t就会对p产生贡献
10 我们用另一个桶b2来维护下行产生的贡献值,对于每个观测点直接读取桶中b2[w[p]-dep[p]]的值即可
11 然后就是有几个注意的点：
12 一：因为每个观察点只会被自己子树中的点影响,所以在开始时先读取桶中的值,在递归回溯前再减去算差值
13 二：离开某个观测点后就要减去对应路径上桶中产生的贡献
14 三：当路径的起点或终点恰好为LCA时,上行下行路径会计算两遍,所以--
15 */
16 #include <bits/stdc++.h>
17 using namespace std;
18 const int N = 3e5 + 7;
19 int n, m;
20 int dep[N], w[N], fa[N][20];//节点深度 每个观察员观察时间 LCA数组
21 int b1[N * 2], b2[N * 2], js[N], dist[N], s[N], t[N], ans[N];
22 //b1,b2分别是是上行下行产生贡献的桶 js是以某个点为起点的路径条数
23 //dist[i]是第i条路径的长度 s[],t[]分别是每条路径的起点终点 ans是答案
24 int tot, tot1, tot2, head[N], head1[N], head2[N];
25 struct edge{
26 int next, to;
27 }e[N * 3], e1[N * 3], e2[N * 3];
28 void add(int u, int v) {//就加基础的边
29 e[++tot] = {head[u], v};
30 head[u] = tot;
31 }
32 void add1(int u, int v) {//把每条路径的终点和该条路径编号连边 用于计算下行贡献
33 e1[++tot1] = {head1[u], v};
34 head1[u] = tot1;
35 }
36 void add2(int u, int v) {//把每条路径起点终点LCA与该条路径编号连边 用于清除
37 e2[++tot2] = {head2[u], v};
38 head2[u] = tot2;
39 }
40 void dfs1(int u) {//第一遍dfs就求出父亲和深度
41 for (int i = 1; (1 << i) <= dep[u]; i++) {
42 fa[u][i] = fa[fa[u][i - 1]][i - 1];
43 }
44 for (int i = head[u]; i; i = e[i].next) {
45 int to = e[i].to;
46 if (to == fa[u][0]) {
47 continue;
48 }
49 fa[to][0] = u;
50 dep[to] = dep[u] + 1;
51 dfs1(to);
52 }
53 }
54 int LCA(int x, int y) {//倍增求LCA
55 if (x == y) {
56 return x;
57 }
58 if (dep[x] < dep[y]) {
59 swap(x, y);
60 }
61 int dd = dep[x] - dep[y];
62 for (int i = 0; i < 20; i++) {
63 if (dd >> i & 1) {
64 x = fa[x][i];
65 }
66 }
67 if (x == y) {
68 return x;
69 }
70 for (int i = 19; i >= 0; i--) {
71 if (fa[x][i] != fa[y][i]) {
72 x = fa[x][i];
73 y = fa[y][i];
74 }
75 }
76 return fa[x][0];
77 }
78 void dfs2(int u) {
79 int t1 = b1[dep[u] + w[u]];//因为每个观察点只会被自己子树中的点影响
80 int t2 = b2[w[u] - dep[u] + N];//所以在开始时先读取桶中的值,在递归回溯前再减去算差值
81 for (int i = head[u]; i; i = e[i].next) {
82 int to = e[i].to;
83 if (to == fa[u][0]) {
84 continue;
85 }
86 dfs2(to);
87 }
88 b1[dep[u]] += js[u];//计算上行贡献 加上以该点为起点的路径条数
89 for (int i = head1[u]; i; i = e1[i].next) {//计算下行贡献
90 int to = e1[i].to;//取出以这个点为终点的路径遍号
91 b2[dist[to] - dep[t[to]] + N]++;///根据公式计算贡献 dist[s,t]-dep[t] = w[u] - dep[u]
92 }
93 ans[u] += b1[w[u] + dep[u]] - t1 + b2[w[u] - dep[u] + N] - t2;//计算差值
94 for (int i = head2[u]; i; i = e2[i].next) {
95 int to = e2[i].to;//取出以改点为LCA的路径编号
96 b1[dep[s[to]]]--; //因为离开当前观察点之后当前贡献就无效了，所以减去
97 b2[dist[to] - dep[t[to]] + N]--;
98 }
99 }
100 int main () {
101 scanf("%d%d", &n, &m);
102 for (int i = 1; i < n; i++) {
103 int u, v;
104 scanf("%d%d", &u, &v);
105 add(u, v);
106 add(v, u);
107 }
108 dep[1] = 1;
109 fa[1][0] = 1;
110 dfs1(1);
111 for (int i = 1; i <= n; i++) {
112 scanf("%d", &w[i]);
113 }
114 for (int i = 1; i <= m; i++) {
115 scanf("%d%d", &s[i], &t[i]);
116 int lca = LCA(s[i], t[i]);
117 dist[i] = dep[s[i]] + dep[t[i]] - 2 * dep[lca];//树上差分
118 js[s[i]]++;
119 add1(t[i], i);
120 add2(lca, i);
121 if (dep[lca] + w[lca] == dep[s[i]]) {
122 ans[lca]--;//这里是因为如果路径的起点或终点恰好为LCA时,上行下行路径会计算两遍,所以--
123 }
124 }
125 dfs2(1);
126 for (int i = 1; i <= n; i++) {
127 printf("%d%c", ans[i], i == n ? '\n' : ' ');
128 }
129 return 0;
130 }
View Code