rt,检查过很多遍,LCA 应该是没有错误,是细节错误吗?
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=5e4;
const int K=20;
int num[N+5],tot;
struct node{
int end;
int nxt;
void add(int u,int v){
end=v;
nxt=num[u];
num[u]=tot;
}
}edge[2*N+5];
int f[N+5][K+5];
int d[N+5];
int n,k;
bool vis[N+5];
void dfs1(int x,int dep){//遍历找父节点
d[x]=dep;
for(int i=num[x];i;i=edge[i].nxt){
int y=edge[i].end;
if(!d[y]){
f[y][0]=x;
dfs1(y,dep+1);
}
}
}
void build(){//建立倍增表
k=log(n)+1;
for(int j=1;j<=k;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
}
int query(int x,int y){//LCA查询
if(d[x]>d[y])
swap(x,y);
for(int i=k;i>=0;i--)
if(d[f[y][i]]>=d[x])
y=f[y][i];
if(x==y)
return x;
for(int i=k;i>=0;i--)
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
return f[x][0];
}
int S[N+5];
void dfs2(int x){//树上差分
vis[x]=true;
for(int i=num[x];i;i=edge[i].nxt){
int y=edge[i].end;
if(!vis[y]){
dfs2(y);
S[x]+=S[y];
}
}
}
int main(){
int m;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
edge[++tot].add(u,v);
edge[++tot].add(v,u);
}
dfs1(1,1);
build();
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
S[u]++;
S[v]++;
S[query(u,v)]--;
S[f[query(u,v)][0]]--;
}
dfs2(1);
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,S[i]);
printf("%d\n",ans);
return 0;
}