自建测试样例全部通过,但是只有6分,实在找不到哪里有问题,谁来帮我看看
#include<bits/stdc++.h>
using namespace std;
vector<int> a[50005];
int n,k,u,v,dfn[50005],st[20][50005],d=1,c[50005],ans=0;
void dfs1(int fa,int ch){ //构建DFN表
st[0][d]=fa;
dfn[ch]=d++;
for(int i=0;i<a[ch].size();i++)
if(fa!=a[ch][i])dfs1(ch,a[ch][i]);
}
void build(){ //构建ST表
int len=log2(n);
for(int i=1;i<=len;i++)
for(int j=1;j<=n-(1<<i)+1;j++)
if(dfn[st[i-1][j]]<dfn[st[i-1][j+(1<<i-1)]])
st[i][j]=st[i-1][j];
else st[i][j]=st[i-1][j+(1<<i-1)];
// for(int i=0;i<=len;i++){
// for(int j=1;j<=n-(1<<i)+1;j++)
// cout<<st[i][j]<<" ";
// cout<<endl;
// }
}
int query(int u,int v){ //ST表查LCA
if(u==v)return v; //区间起点终点相同
u=dfn[u],v=dfn[v];
if(u>v)swap(u,v);
int len=log2(v-u++);
return min(st[len][u],st[len][v-(1<<len)+1]);
}
void dfs2(int fa,int ch){ //最后查询,返回子节点的差分数组权重,加到整个回溯路径
for(int i=0;i<a[ch].size();i++){
if(fa==a[ch][i])continue;
dfs2(ch,a[ch][i]);
c[ch]+=c[a[ch][i]];
}
ans=max(ans,c[ch]);
}
int main(){
freopen("P3128_2.in","r",stdin);
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
dfs1(0,1);
// for(int i=1;i<=n;i++)cout<<dfn[i]<<" ";
// cout<<endl;
// for(int i=1;i<=n;i++)cout<<st[0][i]<<" ";
build();
//cout<<query(4,6);
for(int i=1;i<=k;i++){
scanf("%d%d",&u,&v);
c[u]++,c[v]++;
int lca=query(u,v);
//cout<<lca<<endl;
c[lca]--; //LCA被重复计算,需要减一
c[st[0][dfn[lca]]]--; //LCA父节点减一
}
// for(int i=1;i<=n;i++)cout<<c[i]<<" ";
// cout<<endl;
dfs2(0,1);
cout<<ans<<endl;
//for(int i=1;i<=n;i++)cout<<c[i]<<" ";
return 0;
}