社区讨论

求解这两句话区别;%大佬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 条回复,欢迎继续交流。

正在加载回复...