社区讨论
求解这两句话区别;%大佬orz
P3128[USACO15DEC] Max Flow P参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mi6ur97f
- 此快照首次捕获于
- 2025/11/20 11:09 4 个月前
- 此快照最后确认于
- 2025/11/20 11:09 4 个月前
CPP
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,ans;
int d[100050],f[100050][20],c[100050];
bool vis[50010];
int head[100050],now=1;
struct wfq{
int to,nxt;
}bian[100050];
void Add(int x,int y)
{
bian[now].to=y;
bian[now].nxt=head[x];
head[x]=now;
now++;
return;
}
void dfs(int u)
{
for(int i=head[u];i;i=bian[i].nxt)
{
int v=bian[i].to;
if(!d[v])
{
d[v]=d[u]+1;
f[v][0]=u;
dfs(v);
}
}
}
void Init()
{
for(int i=1;i<=19;i++)
{
for(int j=1;j<=n;j++)
{
f[j][i]=f[f[j][i-1]][i-1];
}
}
return;
}
int lca(int x,int y)
{
c[x]++,c[y]++;
if(d[x]<d[y])swap(x,y);
for(int i=19;i>=0;i--)
{
if(d[f[x][i]]>=d[y])
{
x=f[x][i];
}
}
if(x==y)return y;
for(int i=19;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
void dfs2(int u)
{
vis[u] = 1;
for(int i=head[u];i;i=bian[i].nxt)
{
int v=bian[i].to;
if(!vis[v])//这一句话,这样是对的。
dfs2(v),c[u]+=c[v];
}
ans=max(ans,c[u]);
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
Add(u,v);Add(v,u);
}
dfs(1);Init();
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
int Q=lca(x,y);
c[Q]--;c[f[Q][0]]--;
}
dfs2(1);
printf("%d\n",ans);
return 0;
}
if(v!=f[u][0])//这样就错了.。为什么啊...
回复
共 1 条回复,欢迎继续交流。
正在加载回复...