为什么过不了链的情况
查看原帖
为什么过不了链的情况
117395
Bob_Wang楼主2021/8/2 00:11

RT,代码如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define maxn 1000005
using namespace std;

struct node
{
	int v,next,val;
}tr[maxn<<1];
int n,q,k;
int tot,head[maxn];
int tp,stk[maxn],que[maxn],vis[maxn],fl[maxn],deg[maxn];
ll ans[3];
int mx[maxn],mn[maxn],dw[maxn];//mx[i]是以i的子链的最大值,dw[i]是边i的子节点个数
int idc,fa[maxn],dep[maxn],size[maxn],son[maxn],top[maxn],dfn[maxn],f[maxn][25];

bool cmp(int x,int y)
{
	return dfn[x]<dfn[y];
}

void add(int x,int y,int z)
{
	tot++;
	tr[tot].v=y;
	tr[tot].val=z;
	tr[tot].next=head[x];
	head[x]=tot;
}

void dfs1(int x)
{
	size[x]=1;
	for(int t=head[x];t;t=tr[t].next)
	{
		int y=tr[t].v;
		if(y==fa[x])continue;
		fa[y]=x;
		dep[y]=dep[x]+1;
		dfs1(y);
		size[x]+=size[y];
		if(size[y]>size[son[x]])
		son[x]=y;
	}
}

void dfs2(int x,int tp)
{
	dfn[x]=++idc;
	top[x]=tp;
	if(son[x])dfs2(son[x],tp);
	for(int t=head[x];t;t=tr[t].next)
	{
		int y=tr[t].v;
		if(y==fa[x]||y==son[x])continue;
		dfs2(y,y);
	}
}

void ready(int x)
{
	for(int i=0;i<=20;++i)
	f[x][i+1]=f[f[x][i]][i];
	for(int t=head[x];t;t=tr[t].next)
	{
		int y=tr[t].v;
		if(y==fa[x])continue;
		f[y][0]=x;
		ready(y);
	}
}//预处理倍增数组

int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	return y;
}//求lca

int dis(int x,int y)
{
	int ret=0;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;--i)
	{
		if(dep[f[x][i]]>=dep[y])
		{
			x=f[x][i];
			ret+=(1<<i);
		}
		if(x==y)return ret;
	}
	for(int i=20;i>=0;--i)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
			ret+=(1<<(i+1));
		}
	}
	ret+=2;
	return ret;
}//求两节点间距离

void clear()
{
	memset(head,0,sizeof(head));
	memset(tr,0,sizeof(head));
	tot=0;
}

void insert(int x)
{
	if(!tp)
	{
		stk[++tp]=x;
		return;
	}
	int anc=lca(x,stk[tp]);
	while((tp>1)&&(dep[anc]<dep[stk[tp-1]]))
	{
		add(stk[tp-1],stk[tp],dis(stk[tp-1],stk[tp]));
		deg[stk[tp-1]]++;deg[stk[tp]]++;
		tp--;
	}
	if(dep[anc]<dep[stk[tp]])
	{
		add(anc,stk[tp],dis(anc,stk[tp]));
		deg[stk[tp]]++;deg[anc]++;
		tp--;
	}
	if((!tp)||(stk[tp]!=anc))stk[++tp]=anc;
	stk[++tp]=x;
}//单向边,建立虚树

void dfs3(int x,int lst)//lst记录上一次的边
{
	mx[x]=0;mn[x]=0x3f3f3f3f;
	for(int t=head[x];t;t=tr[t].next)
	{
		int y=tr[t].v,z=tr[t].val;
		dw[t]=0;
		dfs3(y,t);
		dw[lst]+=dw[t];
		if(fl[y])//y是关键点
		{
			if(fl[x])//x也是关键点
			ans[1]=min((int)ans[1],z);
			else
			ans[1]=min((int)ans[1],(int)mn[x]+z);
			mn[x]=min((int)mn[x],z);//更新最小值
		}
		else//y不是关键点
		{
			if(fl[x])//x是关键点
			ans[1]=min((int)ans[1],(int)mn[y]+z);
			else
			ans[1]=min((int)ans[1],(int)mn[x]+mn[y]+z);
			mn[x]=min((int)mn[x],(int)mn[y]+z);
		}
		ans[0]+=z*dw[t]*(k-dw[t]);
		if(deg[x]>1||fl[x])
		ans[2]=max((int)ans[2],(int)mx[x]+mx[y]+z);
		mx[x]=max((int)mx[x],(int)mx[y]+z);//更新最大值
	}
	if(fl[x])dw[lst]++;
	head[x]=0;
	deg[x]=0;
}

void start()
{
	tot=tp=0;
	ans[0]=ans[2]=0;
	ans[1]=0x3f3f3f3f;
	scanf("%d",&k);
	for(int i=1;i<=k;++i)
	{
		scanf("%d",&que[i]);
		fl[que[i]]=1;
	}
	sort(que+1,que+1+k,cmp);//按照dfn排序
	if(que[1]!=1)
	stk[++tp]=1;
	for(int i=1;i<=k;++i)
	insert(que[i]);
	while(--tp)
	{
		add(stk[tp],stk[tp+1],dis(stk[tp],stk[tp+1]));//建立虚树
		deg[stk[tp]]++;deg[stk[tp+1]]++;
	}
	dfs3(1,0);
	for(int i=1;i<=k;++i)
	fl[que[i]]=0;
	for(int i=1;i<=tot;++i)
	dw[i]=0;
	printf("%lld %lld %lld\n",ans[0],ans[1],ans[2]);
}

int main()
{
	//freopen("P4103_5.in","r",stdin);
	//freopen("P4103.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y,1);
		add(y,x,1);
	}
	fa[1]=0;
	dep[1]=1;
	dfs1(1);
	dfs2(1,1);
	ready(1);
	clear();
	scanf("%d",&q);
	for(int i=1;i<=q;++i)
	start();
	return 0;
}
2021/8/2 00:11
加载中...