题解
由于这位大佬似乎afo(?)了,所以我没搞懂那个桶怎么处理,到时候要回来再看一遍
#include <bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
int n, m, cnt, hd[300005], dep[300005], fa[300005][23], w[300005];
int cnt1, cnt2, hd1[300005], hd2[300005];
struct node {
int to;
int nex;
} a1[300005 * 2], a2[300005 * 2], a3[300005 * 2];
int b1[700005], b2[700005], ji[300005], dis[300005], s[300005], t[300005], l[300005], ans[300005];
const int inf = 300005;
void add(int x, int y) {
a1[++cnt].to = y;
a1[cnt].nex = hd[x];
hd[x] = cnt;
}
void add1(int x, int y) {
a2[++cnt1].to = y;
a2[cnt1].nex = hd1[x];
hd1[x] = cnt1;
}
void add2(int x, int y) {
a3[++cnt2].to = y;
a3[cnt2].nex = hd2[x];
hd2[x] = cnt2;
}
void dfs1(int x, int fat) {
fa[x][0] = fat;
dep[x] = dep[fat] + 1;
for (int i = 1; (1 << i) <= dep[x]; i++)
fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (int i = hd[x]; i; i = a1[i].nex) {
int y = a1[i].to;
if (y == fat)
continue;
dfs1(y, x);
}
}
int gl(int x, int y) {
if (x == y)
return x;
if (dep[x] < dep[y])
swap(x, y);
for (int i = 21; i >= 0; i--)
if (dep[fa[x][i]] >= dep[y])
x = fa[x][i];
if (x == y)
return x;
for (int i = 21; i >= 0; i--)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
void dfs2(int x) {
int t1 = b1[w[x] + dep[x]], t2 = b2[w[x] - dep[x] + inf];
for (int i = hd[x]; i; i = a1[i].nex) {
int y = a1[i].to;
if (y == fa[x][0])
continue;
dfs2(y);
}
b1[dep[x]] += ji[x];
for (int i = hd1[x]; i; i = a2[i].nex) {
int y = a2[i].to;
b2[dis[y] - dep[t[y]] + inf]++;
}
ans[x] += b1[w[x] + dep[x]] - t1 + b2[w[x] - dep[x] + inf] - t2;
for (int i = hd2[x]; i; i = a3[i].nex) {
int y = a3[i].to;
b1[dep[s[y]]]--;
b2[dis[y] - dep[t[y]] + inf]--;
}
}
int main() {
scanf("%d%d", &n, &m);
int x, y;
for1(i, 1, n - 1) {
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dep[1] = 1;
fa[1][0] = 1;
dfs1(1, 0);
for1(i, 1, n) scanf("%d", &w[i]);
for1(i, 1, m) {
scanf("%d%d", &s[i], &t[i]);
int lca = gl(s[i], t[i]);
dis[i] = dep[s[i]] + dep[t[i]] - 2 * dep[lca];
ji[s[i]]++;
add1(t[i], i);
add2(lca, i);
if (dep[lca] + w[lca] == dep[s[i]])
ans[lca]--;
}
dfs2(1);
for1(i, 1, n)
printf("%d ", ans[i]);
return 0;
}
标签:NOIP2016,fa,dep,int,2022,lca,P1600,--,for1
From: https://www.cnblogs.com/yyx525jia/p/16770287.html