下面是我的代码,87分,在 #5 #7 碰钉子了。我下载了 #5 的数据,在自己电脑上跑了两遍遍结果都是正确的,但测评机给我打了WA,好神奇,为什么?
//洛谷 P3128 [USACO15DEC] Max Flow P
#include<bits/stdc++.h>
using namespace std;
const int N=50005;
struct node
{
int to,next;
}Edge[N*2];
int n,k,x,y,Et,head[N],di[N],f[N][30],dep[N],t,p[N],ans;
void init()
{
for(int i=1;i<=n;i++)
head[i]=-1;
}
void add(int d1,int d2)
{
Edge[++Et]=(node){d2,head[d1]};
head[d1]=Et;
}
void bfs()
{
f[1][0]=-1;
dep[1]=0;
queue<int>q;
queue<int>fa;
q.push(1);
fa.push(-1);
while(!q.empty())
{
int u=q.front(),ufa=fa.front();
q.pop();
fa.pop();
for(int i=head[u];i!=-1;i=Edge[i].next)
{
if(Edge[i].to!=ufa)
{
dep[Edge[i].to]=dep[u]+1;
f[Edge[i].to][0]=u;
for(int j=1;j<=t;j++)
{
f[Edge[i].to][j]=f[f[Edge[i].to][j-1]][j-1];
}
q.push(Edge[i].to);
fa.push(u);
}
}
}
}
int lca(int s1,int t1)
{
if(s1==t1)
{
return s1;
}
if(dep[s1]<dep[t1])
{
swap(s1,t1);
}
for(int i=t;i>=0;i--)
{
if(dep[f[s1][i]]>=dep[t1])
{
s1=f[s1][i];
}
}
if(s1==t1)
{
return s1;
}
for(int i=t;i>=0;i--)
{
if(f[s1][i]!=f[t1][i])
{
s1=f[s1][i],
t1=f[t1][i];
}
}
return f[s1][0];
}
int dfs(int di1,int di1_father)
{
int di1_yl=di[di1];
for(int i=head[di1];i!=-1;i=Edge[i].next)
{
if(Edge[i].to!=di1_father)
{
di1_yl=di1_yl+dfs(Edge[i].to,di1);
}
}
ans=max(ans,di1_yl);
return di1_yl;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&k);
t=log(n)/log(2)+1;
init();
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
bfs();
for(int i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
di[x]++;
di[y]++;
int nca=lca(x,y);
di[nca]--,di[f[nca][0]]--;
}
dfs(1,-1);
printf("%d",ans);
return 0;
}