社区讨论

求助大佬!!

P3128[USACO15DEC] Max Flow P参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi863c3p
此快照首次捕获于
2025/11/21 09:14
4 个月前
此快照最后确认于
2025/11/21 09:14
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#define MA 50005
using namespace std;
int n,k;
int fis[MA<<2],nex[MA<<2],go[MA<<2],tot;
int p[MA];
int f[MA][25],dep[MA];
int ans=0;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();};
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();};
	return x*f;
}
inline void add(int u,int v){
	nex[++tot]=fis[u];
	fis[u]=tot;
	go[tot]=v;
	return ;
}
inline void deal(int u,int fat){
	int i;
	dep[u]=dep[fat]+1;
	for(i=1;f[u][i];i++){
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int e=fis[u];e;e=nex[e]){
		int v=go[e];
		if(v==fat){
			continue;
		}
		f[v][0]=u;
		deal(v,u);
	}
	return ;
}
inline int lca(int x,int y){
	int i;
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	for(i=20;i>=0;i--){
		if(dep[x]-(1<<i)>=dep[y]){
			x=f[x][i];
		}
		if(x==y){
			return x;
		}
	}
	for(i=20;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
inline void dfs(int u,int fat){
	for(int e=fis[u];e;e=nex[e]){
		int v=go[e];
		if(v==fat){
			continue;
		}
		dfs(v,u);
		p[u]+=p[v];
	}
	ans=max(ans,p[u]);
	return ;
}
int main(){
	int i;
	int x,y;
	n=read();k=read();
	for(i=1;i<n;i++){
		x=read();y=read();
		add(x,y);
		add(y,x);
	}
	deal(1,0);
	for(i=1;i<=k;i++){
		x=read();y=read();
		++p[x];++p[y];--p[lca(x,y)];--p[f[lca(x,y)][0]];
	}
	dfs(1,0);
	printf("%d",ans);
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...