LCA+树上差分20pts求调
查看原帖
LCA+树上差分20pts求调
712794
Azure_Space楼主2023/7/21 20:01

只过了#1#6#8,#2看了数据但数据太大不知道怎么改

#include<bits/stdc++.h>
using namespace std;
int head[50001],cnt=0,f[50001],st[50001][17],cf[50001],sd[50001],maxn=-1,a[50001];
struct node
{
	int to,nxt;
}e[100001];
void add_edge(int u,int v)
{
	e[++cnt]={v,head[u]};
	head[u]=cnt; 
}
void hs(int x,int fa,int sd2)
{
	for(int i=head[x];i;i=e[i].nxt)
	{
		if(e[i].to!=fa)
		{
			f[e[i].to]=x;
			sd[e[i].to]=sd2+1;
			hs(e[i].to,x,sd2+1);
		}
	}
}
int lca(int u,int v)
{
	if(sd[u]<sd[v]) swap(u,v);
	for(int i=16;i>=0;i--)
	{
		if(sd[st[u][i]]>=sd[v]) u=st[u][i];
	}
	for(int i=16;i>=1;i--)
	{
		if(st[u][i]!=st[v][i]) u=st[u][i],v=st[v][i];
	}
	if(u==v) return u;
	else return f[u];
}
void hs2(int x,int fa)
{
	for(int i=head[x];i;i=e[i].nxt)
	{
		if(e[i].to!=fa)
		{
			hs2(e[i].to,x);
			a[x]+=a[e[i].to];
		}
	}
	a[x]+=cf[x];
	maxn=max(maxn,a[x]);
}
int main()
{
	memset(st,0,sizeof(st));
	memset(cf,0,sizeof(cf));
	memset(head,0,sizeof(head));
	memset(e,0,sizeof(e));
	memset(a,0,sizeof(a));
	int n,k,x,y,s,t,l;
	cin>>n>>k;
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x); 
	}
	sd[0]=0,sd[1]=1,f[1]=0;
	hs(1,0,1);
	for(int i=1;i<=n;i++) st[i][0]=f[i];
	for(int i=1;i<=16;i++)
	{
		for(int j=1;j<=n;j++) st[j][i]=st[st[j][i-1]][i-1];
	}
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d",&s,&t);
		cf[s]++,cf[t]++;
		l=lca(s,t);
		cf[l]--,cf[f[l]]--;
	}
	hs2(1,0);
	cout<<maxn;
	return 0;
}

2023/7/21 20:01
加载中...