求调求调求调求调求调求调求调求调
查看原帖
求调求调求调求调求调求调求调求调
655407
WisNourx_楼主2024/1/25 21:25

rt,#1~#10 全 MLE,问题目前出在 dfs1 时跳不出来循环导致的爆空间。

bool _Start;
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cmath>
#include<unordered_map>
using namespace std;

char buf[1<<20], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf, 1, 1<<20, stdin), p1==p2)?EOF:*p1++)
template <typename T>
void read(T &x)
{
	x=0;int f=1;char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-1:1, c=getchar();
	while (isdigit(c)) x=(x<<1)+(x<<3)+c-'0', c=getchar();
	x*=f;
}

typedef long long LL;
const int N=2e5+10;
const int inf=2e9;
int n, m, tsp, q[N], lg, ans[N], b[N];
struct edge{int x, y, pre;}a[N<<1];int alen, last[N<<1];
void ins(int x, int y)
{
	alen++;a[alen]={x, y, last[x]};last[x]=alen;
	alen++;a[alen]={y, x, last[y]};last[y]=alen;
}
edge G[N<<1];int glen, last_g[N<<1];
void ins_g(int x, int y) 
{
	glen++;G[glen]={x, y, last_g[x]};last_g[x]=glen;
	glen++;G[glen]={y, x, last_g[y]};last_g[y]=glen;	
}

int fa[N][19], dfn[N], dep[N], Size[N], stack[N], top;
bool cmp(int n1, int n2) {return dfn[n1]<dfn[n2];}
void init(int x, int f)
{
	dfn[x]=++tsp, Size[x]=1, fa[x][0]=f;
	for (int i=1;i<=lg;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
	for (int k=last[x];k;k=a[k].pre)
	{
		int y=a[k].y;
		if (y==f) continue;
		dep[y]=dep[x]+1;
		init(y, x);Size[x]+=Size[y];
	}
}

int LCA(int x, int y) 
{
	if (dep[x]<dep[y]) swap(x, y);
	for (int i=lg;i>=0;i--) 
		if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if (x==y) return y;
	for (int i=lg;i>=0;i--)
		if (fa[x][i]!=fa[y][i]) x=fa[x][i], y=fa[y][i];
	return fa[x][0];
}

int f[N], g[N];bool v[N];
void query(int x, int y)
{
	int p=y, q=y;
	for (int i=lg;i>=0;i--)
		if (dep[fa[p][i]]>=dep[x]) p=fa[p][i];
	for (int i=lg;i>=0;i--)
	{
		int l=dep[y]-dep[fa[q][i]]+f[y], r=dep[fa[q][i]]-dep[x]+f[x];
		if (dep[fa[q][i]]>dep[x]&&(l<r||(l==r&&g[y]<g[x]))) q=fa[q][i];
	}
	ans[g[y]]+=Size[q]-Size[y];ans[g[x]]-=Size[q];
}

void dfs1(int x, int ff)
{
	f[x]=inf;
	for (int k=last_g[x];k;k=G[k].pre)
	{
		int y=G[k].y, val=dep[y]-dep[x];
		if (y==ff) continue;
		dfs1(y, x);
		if (f[x]>f[y]+val) f[x]=f[y]+val, g[x]=g[y];
		else if (f[y]+val==f[x]) g[x]=min(g[x], g[y]); 
	}
	if (v[x]) f[x]=0, g[x]=x;
}

void dfs2(int x, int ff)
{
	for (int k=last_g[x];k;k=G[k].pre)
	{
		int y=G[k].y, val=dep[y]-dep[x];
		if (y==ff) continue;
		if (f[x]+val<f[y]) f[y]=f[x]+val, g[y]=g[x];
		else if (f[x]+val==f[y]) g[y]=min(g[x], g[y]);
		query(x, y);
		dfs2(y, x);
	}
	ans[g[x]]+=Size[x]; 
	v[x]=last_g[x]=0;
}

bool _End;
int main()
{
//	fprintf(stderr,"Memory: %.4lf Mib\n",abs(&_End-&_Start)/1048576.0);
	freopen("P3233_1.in", "r", stdin);
	memset(last_g, 0, sizeof last_g);
	read(n);lg=log2(n);
	for (int i=1;i<n;i++)
	{
		int x, y;
		read(x), read(y);
		ins(x, y);
	}
	read(m);
	dep[1]=1;init(1, 0);
	for (int t=1;t<=m;t++)
	{
		int k;read(k);glen=0;
		for (int i=1;i<=k;i++) read(q[i]), b[i]=q[i], v[q[i]]=1, ans[q[i]]=0;
		sort(q+1, q+k+1, cmp);stack[top=1]=1;
		if (q[1]!=1) stack[++top]=q[1];
		for (int i=2;i<=k;i++)
		{
			int lca=LCA(q[i], stack[top]);
			while (top>1&&dep[stack[lca]]<dep[stack[top-1]]) ins_g(stack[top-1], stack[top]), top--;
			if (lca!=stack[top]) 
			{
				ins_g(lca, stack[top]);
				if (lca==stack[top-1]) top--;
				else stack[top]=lca;
			}
			stack[++top]=q[i];
		}
		while (top>1) ins_g(stack[top-1], stack[top]), top--;
		dfs1(1, 0);dfs2(1, 0);
		for (int i=1;i<=k;i++)
			printf("%d ", ans[b[i]]);
		puts("");
	}
	return 0;
}
2024/1/25 21:25
加载中...