虚数求调,调了一个月了
查看原帖
虚数求调,调了一个月了
774854
qzmoot楼主2024/7/15 17:02
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define int long long
using namespace std;
const int N=2e6+5,inf=INT_MAX;
int n,q,k,as[N];
int dfn[N],idx,f[N][25],dep[N],st[N],top,siz[N],cur[N];
int ans1,ans2,ans3;
struct node{
	int nxt,v;
}a[N<<1],na[N<<1];
int hd[N],tot,nhd[N],ntot;
int read()
{
	int x=0;
	char ch=getchar();
	while(ch<'0' || ch>'9')ch=getchar();
	while(ch>='0' && ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x;
}
void add_a(int u,int v)
{
	a[++tot].v=v;
	a[tot].nxt=hd[u];
	hd[u]=tot;
}
void add_n(int u,int v)
{
	na[++ntot].v=v;
	na[ntot].nxt=nhd[u];
	nhd[u]=ntot;
}
void dfs(int u,int fa)
{
	dfn[u]=++idx;
	dep[u]=dep[fa]+1;
	for(int i=1;(1<<i)<=dep[u];i++)
		f[u][i]=f[f[u][i-1]][i-1];
	for(int i=hd[u];i;i=a[i].nxt)
	{
		int v=a[i].v;
		if(v==fa)
			continue;
		f[v][0]=u;
		dfs(v,u);
	}
}
int lca(int x,int y)
{
	if(dep[x]>dep[y])
		swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[x]<=dep[y]-(1<<i))
			y=f[y][i];
	if(x==y)
		return x;
	for(int i=20;i>=0;i--)
	{
		if(f[x][i]==f[y][i])
			continue;
		else
			x=f[x][i],y=f[y][i];
	}
	return f[x][0];
}
bool cmp(int x,int y)
{
	return dfn[x]<dfn[y];
}
pair<int,int> dfs1(int u,int las)
{
	int max1=u,max2=-1,min1=inf,min2=inf,fl=cur[u],nxt=fl?u:las;
	siz[u]=cur[u];
	if(fl && las!=-1 && u!=las)
		ans2=min(ans2,dep[u]-dep[las]);
	if(fl)
		min1=u;
	for(int i=nhd[u];i;i=na[i].nxt)
	{
		int v=na[i].v;
		pair<int,int> ret=dfs1(v,nxt);
		if(ret.fi>max1)
			max2=max1,max1=ret.fi;
		else if(ret.fi>max2)
			max2=ret.fi;
		if(ret.se<min1)
			min2=min1,min1=ret.se;
		else if(ret.se<min2)
			min2=ret.se;
		siz[u]+=siz[v];
		ans1+=(k-siz[v])*siz[v]*(dep[v]-dep[u]);
	}
	nhd[u]=0;
	if(min1!=inf && min2!=inf)
		ans2=min(ans2,dep[min1]-dep[u]+dep[min2]-dep[u]);
	if(max2!=-1)
		ans3=max(ans3,dep[max1]-dep[u]+dep[max2]-dep[u]);
	return mp(max1,min1);
}
/*
10 
2 1 
3 2 
4 1 
5 2 
6 4 
7 5 
8 6 
9 7 
10 9
1
3 2 5 4

*/
signed main()
{
	freopen("test.in","r",stdin);
	n=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		add_a(u,v),add_a(v,u);
	}
	dfs(1,0);
	q=read();
	while(q--)
	{
		k=read();
		memset(cur,0,sizeof cur);
		ntot=0;
		for(int i=1;i<=k;cur[as[i]]=1,i++)
			as[i]=read();
		sort(as+1,as+1+k,cmp);
		top=0;
		st[++top]=as[1];
		for(int i=2;i<=k;i++)
		{
			int u=as[i];
			int l=lca(st[top],u);
			while(1)
			{
				if(dep[l]>=dep[st[top-1]])
				{
					if(l!=st[top])
					{
						add_n(l,st[top]);
						if(l!=st[top-1])
							st[top]=l;
						else
							top--;
					}
					break;
				}
				else
				{
					add_n(st[top-1],st[top]);
					top--;
				}
			}
			st[++top]=u;
		}
		while(--top)
			add_n(st[top],st[top+1]);
		ans1=0,ans2=inf,ans3=0;
		dfs1(st[1],cur[st[1]]?st[1]:-1);
		printf("%lld %lld %lld\n",ans1,ans2,ans3);
	}
	return 0;
}

在第一个dfs的lca预处理中,我奇怪地在#7上re了,但是评测结果显示wa。#9,#10 tle,怀疑是跟#7一样是死循环,但被判断成tle。

2024/7/15 17:02
加载中...