MLE*7悬关求调
查看原帖
MLE*7悬关求调
606278
封禁用户楼主2024/12/18 23:22
// 1<=n<=1e6 1<=q<=5e4 sum(k)<=2*n 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e6+5;

int cnt=0;
int f[MAXN][35],dep[MAXN],dfn[MAXN],st[MAXN],siz=0,maxn=0,minn=1e9,numm,signum[MAXN];
vector<int> e[MAXN],e1[MAXN];
vector<pair<int,int> > v;
bool vis[MAXN],vis1[MAXN];

void dfs(int id,int fa){
	dfn[id]=++cnt;
	f[id][0]=fa;
	if (!fa) dep[id]=0;
	else dep[id]=dep[fa]+1;
	for (int i=1;i<=30;i++)
		f[id][i]=f[f[id][i-1]][i-1];
	for (int i:e[id]) if (i!=fa and i!=id) dfs(i,id);
}

pair<int,int> lca(int x,int y){
	if (dep[x]<dep[y]) swap(x,y);
	int sum=0;
	for (int i=30;i>=0;i--)
		if (dep[f[x][i]]>=dep[y] and f[x][i])
			sum+=(1<<i),x=f[x][i];
			
	if (x==y) return {x,sum};
	
	for (int i=30;i>=0;i--)
		if (f[x][i]!=f[y][i] and f[x][i] and f[y][i])
			sum+=(1<<(i+1)),x=f[x][i],y=f[y][i];
	
	return {f[x][0],sum+2};
}

int maxx(int id,int fa){
	int max1=0,max2=0;
	for (int i:e1[id]){
		if (i!=fa and i!=id){
			int tmp=maxx(i,id);
			tmp+=dep[i]-dep[id];
			if (tmp>max1){
				max2=max1;
				max1=tmp;
			}
			else if (tmp>max2) max2=tmp;
		}
	}
	maxn=max(max1+max2,maxn);
	return max1;
}

int minx(int id,int fa){
	bool fg=0;
	int min1=1e9,min2=1e9;
	for (int i:e1[id]){
		if (i!=fa and i!=id){
			int tmp=minx(i,id);
			fg=1;
			tmp+=dep[i]-dep[id];
			if (tmp<min1){
				min2=min1;
				min1=tmp;
			}
			else if (tmp<min2) min2=tmp;
		}
	}
	// cout << "=========" << id << ' ' << min1 << ' ' << min2 << endl;
	if (!fg) return 0;
	if (min2==1e9) min2=0;
	minn=min(min1+min2,minn);
	return min1;
}

int get_signum(int id,int fa){
	if (signum[id]!=-1) return signum[id];
	int res=0;
	for (int i:e1[id])
		if (i!=fa and i!=id)
			res+=get_signum(i,id);
	return signum[id]=res+vis1[id];
}

int sumx(int id,int fa){
	int res1=numm-get_signum(id,fa);
	int sum=0;
	for (int i:e1[id])
		if (i!=fa and i!=id)
			sum+=sumx(i,id);
	return res1*(dep[id]-dep[fa])*(id!=1)+sum;
}

int main(){
	int n;
	scanf("%d",&n);
	for (int i=1;i<n;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(1,0);
	int q;
	scanf("%d",&q);
	for (int i=1;i<=q;i++){
		memset(vis,0,sizeof(vis));
		memset(vis1,0,sizeof(vis1));
		memset(signum,-1,sizeof(signum));
		v.clear();
		scanf("%d",&numm);
		for (int j=1;j<=numm;j++){
			int tmp;
			scanf("%d",&tmp);
			v.push_back({dfn[tmp],tmp});
			vis1[tmp]=1;
		}
		sort(v.begin(),v.end());
		siz=0;
		for (int j=1;j<=n;j++) e1[j].clear();
		for (auto j:v){
			int k=j.second;
			if (siz>=1){
				auto z=lca(k,st[siz]);
				e1[st[siz]].push_back(z.first);
				e1[z.first].push_back(st[siz]);
				e1[k].push_back(z.first);
				e1[z.first].push_back(k);
				st[siz]=z.first;
			}
			if (vis[k]) continue;
			st[++siz]=k;
			vis[k]=1;
		}
		maxn=0,minn=1e9;
		maxx(st[1],0);
		minx(st[1],0);
		printf("%d %d %d\n",sumx(st[1],0),maxn,minn);
	}
	
	return 0;
} 

https://www.luogu.com.cn/record/195093251

2024/12/18 23:22
加载中...