关于P3233
  • 板块灌水区
  • 楼主Silent1019
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/11 20:22
  • 上次更新2024/5/11 22:28:13
查看原帖
关于P3233
375337
Silent1019楼主2024/5/11 20:22

巨佬求调,样例1、2、4行对了,但3、5行全输出0

#include<bits/stdc++.h>
using namespace std;
#define INF 2147483647
const int N=3e5+10;
struct Edge{
	int v,next;
}e1[N<<1],e2[N<<1];
int head1[N<<1],tot1,head2[N<<1],tot2;
inline int add1(int u,int v)
{
	tot1++;
	e1[tot1].v=v; e1[tot1].next=head1[u];
	head1[u]=tot1;
}
inline int add2(int u,int v)
{
	tot2++;
	e2[tot2].v=v; e2[tot2].next=head2[u];
	head2[u]=tot2;
}
int n,m,q,a[N],k[N];
int g[N],dp[N],ans[N];
bool vis[N];
int u,v;
int idx,dep[N],dfn[N],siz[N],fa[N][20];
int top,sta[N];
inline bool cmp(int x,int y)
{
	return dfn[x]<dfn[y];
}
inline void dfs(int u)
{
	dfn[u]=++idx; siz[u]=1;
	for(int i=1;i<=19;i++)
		fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head1[u];i;i=e1[i].next)
	{
		int e=e1[i].v;
		if(e!=fa[u][0])
		{
			fa[e][0]=u;
			dep[e]=dep[u]+1;
			dfs(e);
			siz[u]+=siz[e];
		}
	}
}
inline int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;i--)
		if(dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
	if(x==y) return x;
	for(int i=19;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
inline void insert(int u)
{
	if(top==0)
	{
		top=1;
		sta[top]=u;
		return ;
	}
	int l=lca(sta[top],u);
	while(top>1&&dep[l]<dep[sta[top-1]])
	{
		add2(sta[top-1],sta[top]);
		add2(sta[top],sta[top-1]);
		top--;
	}
	if(dep[l]<dep[sta[top]])
	{
		add2(l,sta[top]);
		add2(sta[top],l);
		top--;
	}
	if(top==0||sta[top]!=l) sta[++top]=l;
	top++; sta[top]=u;
}
inline void dfs1(int u,int f)
{
	dp[u]=INF;
	for(int i=head2[u];i;i=e2[i].next)
	{
		int e=e2[i].v;
		if(e==f) continue;
		dfs1(e,u);
		int dis=dep[e]-dep[u];
		if(dp[e]+dis<dp[u]) dp[u]=dp[e]+dis,g[u]=g[e];
		else if(dp[e]+dis==dp[u]) g[u]=min(g[u],g[e]);
	}
	if(vis[u]) dp[u]=0,g[u]=u;
}
inline void calc(int x,int y)
{
	int u=y,e=y;
	for(int i=19;i>=0;i--)
		if(dep[fa[u][i]]>dep[x]) u=fa[u][i];
	ans[g[x]]-=siz[u];
	for(int i=19;i>=0;i--)
	{
		int llen=dep[y]-dep[fa[e][i]]+dp[y],rlen=dep[fa[e][i]]-dep[x]+dp[x];
		if(dep[fa[e][i]]>dep[x]&&(llen<rlen||(llen==rlen&&g[y]<g[x]))) e=fa[e][i];
	}
	ans[g[y]]+=siz[e]-siz[y]; ans[g[x]]+=siz[u]-siz[e];
}
inline void dfs2(int u,int f)
{
	for(int i=head2[u];i;i=e2[i].next)
	{
		int e=e2[i].v;
		if(e==f) continue;
		int dis=dep[e]-dep[u];
		if(dp[u]+dis<dp[u]) dp[e]=dp[u]+dis,g[e]=g[u];
		else if(dp[u]+dis==dp[e]) g[e]=min(g[e],g[u]);
		calc(u,e);
		dfs2(e,u);
	}
	ans[g[u]]+=siz[u];
	vis[u]=0; head2[u]=0;
}
int main()
{

	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add1(u,v); add1(v,u);
	}
	dep[1]=1;
	dfs(1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&q);
		for(int j=1;j<=q;j++)
		{
			scanf("%d",&a[j]);
			vis[a[j]]=1; ans[a[j]]=0;
			k[j]=a[j];
		}
		sort(a+1,a+q+1,cmp);
		tot2=0;
		top=1; sta[top]=a[1];
		for(int j=2;j<=q;j++)
			insert(a[j]);
		while(top>1)
		{
			add2(sta[top],sta[top-1]);
			add2(sta[top-1],sta[top]);
			top--;
		}
		dfs1(1,0); dfs2(1,0);
		for(int j=1;j<=q;j++)
			printf("%d ",ans[k[j]]);
		printf("\n");
	}
	return 0;
}
2024/5/11 20:22
加载中...