54分求助,其他点都是tle QAQ
查看原帖
54分求助,其他点都是tle QAQ
590801
clown__楼主2023/4/23 20:55
#include <iostream>
using namespace std;
const int N=1e6+10;
int head[N],cnt1;
struct Edge
{
	int to,next;
}edge[N];
void addedge(int u,int v)
{
	cnt1++;
	edge[cnt1].to=v;
	edge[cnt1].next=head[u];
	head[u]=cnt1;
}
int dep[N],fa[N],son[N],siz[N];
void dfs1(int x)
{
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to;
		if(to==fa[x]) continue;
		dep[to]=dep[x]+1;
		fa[to]=x;
		dfs1(to);
		siz[x]+=siz[to];
		if(siz[to]>siz[son[x]]) son[x]=to;
	}
}
int cnt2,id[N],top[N];
void dfs2(int x,int rt)
{
	id[x]=++cnt2;
	top[x]=rt;
	if(son[x]) dfs2(son[x],rt);
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to;
		if(to==son[x]||to==fa[x]) continue;
		dfs2(to,to);
	}
}
int cha[N];
void make(int l,int r)
{
	cha[l]++;
	cha[r+1]--;
}
void add(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		make(id[top[u]],id[u]);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]) swap(u,v);
	make(id[v],id[u]);
}
void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		addedge(u,v);
		addedge(v,u);
	}
	dfs1(1);
	dfs2(1,1);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	int ans=0,now=0;
	for(int i=1;i<=n;i++)
	{
		now+=cha[i];
		ans=max(ans,now);
	}
	cout<<ans<<"\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}
2023/4/23 20:55
加载中...