只有6分,求助
查看原帖
只有6分,求助
924195
254391liyi楼主2023/8/1 14:09
#include<iostream>
#include<vector>
using namespace std;
const int N=1e5+10;
vector<int>arr[N];
int num[N],n,m,sum[N],d[N],f[N][32],ans[N];

inline int read(){ //快读
	int s=0;
	char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	while (c>='0' && c<='9') s=s*10+c-'0',c=getchar();
	return s;
}

inline void dfs(int u,int fa,int dep){
	d[u]=dep;
	f[u][0]=fa;
	for(int i=1;i<21;i++){
		if((1<<i)>=dep)break;
		f[u][i]=f[f[u][i-1]][i-1];
	}
	int k=arr[u].size();
	for(int i=0;i<k;i++){
		int x=arr[u][i];
		if(x==fa)arr[u][i]=0;
		else dfs(x,u,dep+1);
	}
}

inline int query(int a,int b){
	if(d[a]<d[b])swap(a,b);
	int k=d[a]-d[b];
	for(int i=0;i<21;i++){
		if((k>>i)&1)a=f[a][i];
	}
	if(a==b)return a;
	for(int i=21;i>=0;i++){
		if((1<<i)<d[a]&&d[a]!=d[b])a=f[a][i],b=f[b][i];
	}
	return f[a][0];
}

inline void dfs2(int u){
	int k=arr[u].size();
	for(int i=0;i<k;i++){
		int x=arr[u][i];
		sum[x]+=sum[u]+num[x]+ans[u];
		dfs2(x);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		arr[x].push_back(y);
		arr[y].push_back(x);
	}
	dfs(1,0,1);
	while(m--){
		int a=read(),b=read();
		int c=query(a,b);
		num[c]++;
		if(c!=a)ans[a]--;
		if(c!=b)ans[b]--;
	}
	sum[1]=num[1];
	dfs2(1);
//	for(int i=1;i<=n;i++)cout<<num[i]<<" ";
//	cout<<endl;
	int max=0;
	for(int i=1;i<=n;i++)if(sum[i]>max)max=sum[i];
	cout<<max;
	return 0;
}
2023/8/1 14:09
加载中...