6pts,Tarjan求调
查看原帖
6pts,Tarjan求调
1232696
zbbfans楼主2024/11/8 17:41
#include<bits/stdc++.h>
using namespace std;
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-48;ch=getchar();}
	return x*f;
}
inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else print(x/10),putchar(x%10+'0');
}
int ans;
int n,k;
int x,y;
int fa[200010];
int cf[200010];
int xx[200010],yy[200010];
int aans[200010];
bool vis[200010];
vector<pair<int,int> > q[200010];
int E,head[200010],nxt[200010],to[200010];
inline int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
inline void add(int a,int b){
	E++;
	to[E]=b;
	nxt[E]=head[a];
	head[a]=E;
}
inline void Tarjan(int u){
	vis[u]=true;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(!vis[v]){
			Tarjan(v);
			fa[v]=u;
		}
	}
	for(auto p : q[u]){
		int v=p.first,i=p.second;
		if(vis[v]) aans[i]=find(v);
	}
}
inline void dfs(int u,int f){
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==f) continue;
		dfs(v,u);
		cf[u]+=cf[v];
	}
	ans=max(ans,cf[u]);
}
int main(){
	n=read(),k=read();
	for(int i=1;i<n;i++){
		fa[i]=i;
		x=read(),y=read();
		add(x,y);
		add(y,x);
	}
	fa[n]=n; 
	for(int i=1;i<=k;i++){
		x=read(),y=read();
		q[x].push_back(make_pair(y,i));
		q[y].push_back(make_pair(x,i));
		xx[i]=x;
		yy[i]=y;
		cf[x]++;cf[y]++;
	}
	Tarjan(1);
	for(int i=1;i<=k;i++){ 
		cf[aans[i]]--;cf[fa[aans[i]]]--;
	}
	dfs(1,0);
	print(ans);
	return 0;
}
2024/11/8 17:41
加载中...