30pts求调,只有链是对的
查看原帖
30pts求调,只有链是对的
864310
zyn0309楼主2024/10/18 20:46
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10;
int idx2,head2[N],idx,head[N],n,dep[N],top[N],siz[N],son[N],fa[N],h[N],id[N],cnt,sum[N],maxlen[N],minlen[N],k;
bool p[N];
struct edge{
	int to,nxt;
}e[N],e2[N];
void add(int u,int v){
	e[++idx].nxt=head[u];
	e[idx].to=v;
	head[u]=idx;
}
void add2(int u,int v){
	e2[++idx2].nxt=head2[u];
	e2[idx2].to=v;
	head2[u]=idx2;
}
void dfs(int u){
	id[u]=++cnt;
	siz[u]=1;
	dep[u]=dep[fa[u]]+1;
    for(int i=head[u];i;i=e[i].nxt){
      int v=e[i].to;
      if(v==fa[u])continue;
      fa[v]=u;
      dfs(v);
      siz[u]+=siz[v];
      if(siz[v]>=siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int t){
	top[u]=t;
	if(!son[u])return;
	dfs2(son[u],t);
	for(int i=head[u];i;i=e[i].nxt){
	  int v=e[i].to;
	  if(v==fa[u]||v==son[u])continue;
	  dfs2(v,v);
	}
}
int getlca(int a,int b){
	while(top[a]!=top[b]){
	  if(dep[top[a]]<dep[top[b]])swap(a,b);
	  a=fa[top[a]];
	}
	if(dep[a]<dep[b])return a;
	else return b;
}
bool cmp(int a,int b){
	return id[a]<id[b];
}
int sta[N],len,sum2,mi,ma;
void dp(int u){
	sum[u]=0;
	if(p[u])minlen[u]=0;
	else minlen[u]=1e9;
	if(p[u])maxlen[u]=0;
	else maxlen[u]=-1e9;
	if(p[u])siz[u]=1;
	else siz[u]=0;
	for(int i=head2[u];i;i=e2[i].nxt){
	  int v=e2[i].to;
	  dp(v);
	  siz[u]+=siz[v];
	  ma=max(ma,maxlen[v]+maxlen[u]+dep[v]-dep[u]);
	  maxlen[u]=max(maxlen[u],maxlen[v]+dep[v]-dep[u]);
	  mi=min(mi,minlen[u]+minlen[v]+dep[v]-dep[u]);
	  minlen[u]=min(minlen[u],minlen[v]+dep[v]-dep[u]);
	  sum[u]+=sum[v]+siz[v]*(dep[v]-dep[u]);
	}
	for(int i=head2[u];i;i=e2[i].nxt){
	  int v=e2[i].to;
	  sum2+=(sum[v]+siz[v]*(dep[v]-dep[u]))*(siz[u]-siz[v]);
	}
	head2[u]=0;
}
void getans(){
	idx2=0;
	sum2=ma=0;
	mi=1e9;
	sort(h+1,h+1+k,cmp);
	len=1;
	sta[len]=1;
	for(int i=1;i<=k;++i){
	  int lca=getlca(h[i],sta[len]);
	  if(h[i]==1)continue;
	  if(lca!=sta[len]){
	  	while(id[lca]<id[sta[len-1]]){
	  	  add2(sta[len-1],sta[len]);
	  	  --len;
		}
		if(id[lca]!=id[sta[len-1]]){
		  add2(sta[len-1],sta[len]);
		  sta[len]=lca;
		}
		else{
		  add2(sta[len-1],sta[len]);
		  --len;
		}
	  }
	  sta[++len]=h[i];
	}
	for(int i=1;i<len;++i)add2(sta[i],sta[i+1]);
	dp(1);
	cout<<sum2<<" "<<mi<<" "<<ma<<"\n";
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	int u,v;
	for(int i=1;i<n;++i){
	  cin>>u>>v;
	  add(u,v);
	  add(v,u);
	}
	dfs(1);
	dfs2(1,1);
	int m;
	cin>>m;
	for(int i=1;i<=m;++i){
	  cin>>k;
	  for(int j=1;j<=k;++j){
	  	cin>>h[j];
	  	p[h[j]]=1;
	  }
	  getans();
	  for(int j=1;j<=k;++j)p[h[j]]=0;
	}
	return 0;
}
2024/10/18 20:46
加载中...