Phrvth @ 2023-07-26 23:02:36
不知道Lca有没有问题,着重看吧
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 7, Siz = 3e4 + 7;
int n, m, W[MAXN], S[MAXN], T[MAXN];
struct Node {
int nxt, to;
}Edge1[2 * MAXN], Edge2[2 * MAXN], Edge3[2 * MAXN];
int H1[MAXN], H2[MAXN], H3[MAXN], E1, E2, E3;
void add1(int from , int to) {
Edge1[++ E1] = Node {H1[from], to};
H1[from] = E1;
}
void add2(int from , int to) {
Edge2[++ E2] = Node {H2[from], to};
H2[from] = E2;
}
void add3(int from , int to) {
Edge3[++ E3] = Node {H3[from], to};
H3[from] = E3;
}
int Dep[MAXN], F[MAXN][30];
void dfs1(int u, int fa) {
Dep[u] = Dep[fa] + 1; F[u][0] = fa;
for (int i = 1; i <= log2(Dep[u]); i ++)
F[u][i] = F[F[u][i - 1]][i - 1];
for (int i = H1[u]; i; i = Edge1[i].nxt) {
int v = Edge1[i].to;
if (v == fa) continue;
dfs1(v, u);
}
}
int Lca(int x, int y) {
if (Dep[x] < Dep[y]) swap(x, y);
while (Dep[x] > Dep[y]) x = F[x][(int)log2(Dep[x] - Dep[y])];
if (x == y) return x;
for (int i = log2(Dep[x]); i >= 0; i --)
if (F[x][i] != F[y][i]) x = F[x][i], y = F[y][i];
return F[x][0];
}
int T1[2 * MAXN], T2[2 * MAXN], V[MAXN], Dis[MAXN], Ans[MAXN];
/*
对于每个节点 s,它作为起点的代价是固定的,即为多少个点作为起点
但它作为终点的代价并不是固定的,每条路径以 s 为终点的代价都是不一样的
lca也一样
有两点,答案为差值,和 lca 往上的点都没用
最后判下当链的起点就为 lca 的情况,减掉即可
*/
void dfs2(int u) {
int t1 = T1[W[u] + Dep[u]], t2 = T2[W[u] - Dep[u] + Siz];
for (int i = H1[u]; i; i = Edge1[i].nxt) {
int v = Edge1[i].to;
if (v == F[u][0]) continue;
dfs2(v);
}
T1[Dep[u]] += V[u];//起点的贡献
for (int i = H2[u]; i; i = Edge2[i].nxt) {
int v = Edge2[i].to;//注意,这里的v为边的编号
T2[Dis[v] - Dep[T[v]] + Siz] ++;//终点的贡献
}
Ans[u] += T1[W[u] + Dep[u]] - t1 + T2[W[u] - Dep[u] + Siz] - t2;
for (int i = H3[u]; i; i = Edge3[i].nxt) {
int v = Edge3[i].to;
T1[Dep[S[v]]] --; T2[Dis[v] - Dep[T[v]] + Siz] --;
}
}
int main () {
cin >> n >> m;
for (int i = 1, u, v; i < n; i ++) {
cin >> u >> v; add1(u, v); add1(v, u);
}
dfs1(1, 0);
for (int i = 1; i <= n; i ++) cin >> W[i];
for (int i = 1; i <= m; i ++) {
cin >> S[i] >> T[i];
int lca = Lca(S[i], T[i]);
Dis[i] = Dep[S[i]] + Dep[T[i]] - 2 * Dep[lca]; V[S[i]] ++;
add2(T[i], i); add3(lca, i);
if (Dep[lca] + W[lca] == Dep[S[i]]) Ans[lca] --;
}
dfs2(1);
for (int i = 1; i <= n; i ++) cout << Ans[i] << ' ';
return 0;
}
by Phrvth @ 2023-07-26 23:22:21
此贴结
by comcopy @ 2023-09-09 14:33:56
@Phrvth 什么问题求告知
by Phrvth @ 2023-09-10 00:29:20
@comcopy