@[ywjzxx](/user/175045)
1. head 应该是 N 的大小,它对应的是每个点,而不是每条边。
1. find 函数中,当调整 x 和 y 的高度以使它们处于同一高度时,最终判断 x 是否等于 y 应该在调整高度之后进行。但主要问题不在这里,部分逻辑其实是正确的,只是提醒一下顺序逻辑。
1. 你这代码在处理两节点的公共祖先时,减少了公共祖先和其父节点的 point 值,这部分是正确的。但确保公共祖先的计算是正确的。
其他部分应该都是正确的。
正解:
```cpp
#include<iostream>
using namespace std;
const int N = 50005; // 根据题目要求调整数组大小
int n, k;
struct tnode{
int v, next;
} edge[2 * N]; // 边的数量应该是节点的两倍
int head[N], depth[N], fa[N][21], point[N];
int cnt = 0, ans = 0;
void add(int u, int v){
edge[++cnt] = {v, head[u]};
head[u] = cnt;
}
void dfs(int u, int father){
depth[u] = depth[father] + 1;
fa[u][0] = father;
for (int i = 1; i <= 20; i++)
fa[u][i] = fa[fa[u][i-1]][i-1];
for (int i = head[u]; i; i = edge[i].next){
int y = edge[i].v;
if (y != father) dfs(y, u);
}
}
void dfs2(int u, int father){
for (int i = head[u]; i; i = edge[i].next){
int y = edge[i].v;
if (y != father){
dfs2(y, u);
point[u] += point[y];
}
}
ans = max(ans, point[u]);
}
int find(int x, int y){
if (depth[x] < depth[y]) swap(x, y);
for (int i = 20; i >= 0; i--)
if (depth[fa[x][i]] >= depth[y])
x = fa[x][i];
if (x == y) return x;
for (int i = 20; i >= 0; i--){
if (fa[x][i] != fa[y][i]){
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
int main(){
cin >> n >> k;
for (int i = 1; i < n; i++){
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
dfs(1, 0);
for (int i = 1; i <= k; i++){
int a, b;
cin >> a >> b;
int lca = find(a, b);
point[a]++;
point[b]++;
point[lca]--;
if (lca != 1) point[fa[lca][0]]--; // 仅当 LCA 不是根节点时减少
}
dfs2(1, 0);
cout << ans << endl;
return 0;
}
```
如此,就可以AC了
by TPJ_XiaoJing @ 2024-03-09 12:45:36
@[TPJ_XiaoJing](/user/1280061) 太感谢这位大佬了,自己找bug两个小时没找出来问题
by ywjzxx @ 2024-03-09 15:27:19