评测记录

思路如下：

对于每个询问，通过单调栈建出虚树，然后在虚树上点分治。

点分治维护几个信息：

• gsiz 表示当前已经合并进点分治重心 gvt 的子树中有多少个关键点；
• gdis 表示当前已经合并进点分治重心的子树中的关键点到分治重心的总距离；
• gdl 表示当前已经合并进点分治重心的子树中的关键点到分治重心的距离最小值；
• gdr 表示当前已经合并进点分治重心的子树中的关键点到分治重心的距离最大值；

接下来考虑分治重心一个没有被合并进分治重心的子树：

• tsiz 表示这棵子树中有多少个关键点；
• tdis 表示这棵子树的所有关键点到分治重心的总距离；
• tdl 表示这棵子树的所有关键点到分治重心的距离的最小值；
• tdr 表示这棵子树的所有关键点到分治重心的距离的最大值；

合并的时候就按照代码中的式子合并就行了。

但是五颜六色 $30\text{pts}$，还请各位大佬看看是哪里出问题了。所有“只过了链”的警示后人好像都不适用于这个做法？

#include<cstdio>
#include<algorithm>
const int MAXN=1e6+7;
struct Edge{int v,nxt;}e[MAXN<<1];
int n,Q,dfn[MAXN],tim,dep[MAXN],fa[MAXN][21],pc,p[MAXN],h[MAXN],idx=1,stk[MAXN],tp,gvt,sizgvt=1e9,blk,siz[MAXN],tsiz,tdl,tdr,usd[MAXN],tu,ansl,ansr;
long long tdis,ans;
bool isq[MAXN],vis[MAXN];
inline void add(int u,int v){
	e[++idx]={v,h[u]},h[u]=idx;
}
void DFS_lca(int u){
	dep[u]=dep[fa[u][0]]+1;
	for(int i=1;i<21;++i)
		fa[u][i]=fa[fa[u][i-1]][i-1];
	dfn[u]=++tim;
	for(int i=h[u],v=e[i].v;i;v=e[i=e[i].nxt].v)
		if(!dfn[v])
			fa[v][0]=u,DFS_lca(v);
}
inline int LCA(int u,int v){
	if(dep[u]<dep[v])
		std::swap(u,v);
	for(int i=20;~i;--i)
		if(dep[fa[u][i]]>=dep[v])
			u=fa[u][i];
	if(u==v)
		return v;
	for(int i=20;~i;--i)
		if(fa[u][i]!=fa[v][i])
			u=fa[u][i],v=fa[u][i];
	return fa[u][0];
}
void DFS_gvt(int u,int ff){
	siz[u]=1;
	int mx=0;
	for(int i=h[u],v=e[i].v;i;v=e[i=e[i].nxt].v)
		if(v!=ff&&!vis[v])
			DFS_gvt(v,u),siz[u]+=siz[v],mx=std::max(mx,siz[v]);
	mx=std::max(mx,blk-siz[u]);
	if(mx<sizgvt)
		gvt=u,sizgvt=mx;
}
void DFS_dis(int u,int ff,int ds){
	if(isq[u])
		++tsiz,tdis+=ds,tdl=std::min(tdl,ds),tdr=std::max(tdr,ds);
	for(int i=h[u],v=e[i].v;i;v=e[i=e[i].nxt].v)
		if(v!=ff&&!vis[v])
			DFS_dis(v,u,ds+abs(dep[u]-dep[v]));
}
void DFS(int u){
	vis[u]=true,usd[++tu]=u;
	int gsiz=isq[u],tblk=blk,gdl=isq[u]?0:1e9,gdr=0;
	long long gdis=0;
	for(int i=h[u],v=e[i].v;i;v=e[i=e[i].nxt].v)
		if(!vis[v])
			tsiz=0,tdl=1e9,tdr=0,tdis=0,
			DFS_dis(v,u,abs(dep[u]-dep[v])),
			ans+=tsiz*gdis+gsiz*tdis,ansl=std::min(ansl,gdl+tdl),ansr=std::max(ansr,gdr+tdr),
			gsiz+=tsiz,gdis+=tdis,gdl=std::min(gdl,tdl),gdr=std::max(gdr,tdr);
	for(int i=h[u],v=e[i].v;i;v=e[i=e[i].nxt].v)
		if(!vis[v])
			gvt=0,sizgvt=1e9,blk=siz[v]>siz[u]?tblk-siz[u]:siz[v],DFS_gvt(v,u),DFS(gvt);
}
int main(){
	scanf("%d",&n);
	for(int i=1,u,v;i<n;++i)
		scanf("%d%d",&u,&v),add(u,v),add(v,u);
	DFS_lca(1),idx=1;
	for(int i=1;i<=n;++i)
		h[i]=0;
	scanf("%d",&Q);
	while(Q--){
		scanf("%d",&pc),ans=0,ansl=1e9,ansr=-1;
		for(int i=1;i<=pc;++i)
			scanf("%d",&p[i]),isq[p[i]]=true;
		std::sort(p+1,p+pc+1,[&](const int x,const int y){return dfn[x]<dfn[y];}),stk[tp=1]=p[1];
		for(int i=2,lc;i<=pc;++i){
			lc=LCA(p[i],stk[tp]);
			while(dep[lc]<dep[stk[tp-1]])
				add(stk[tp-1],stk[tp]),add(stk[tp],stk[tp-1]),--tp;
			if(lc!=stk[tp]){
				add(lc,stk[tp]),add(stk[tp],lc);
				if(lc!=stk[tp-1])
					stk[tp]=lc;
				else
					--tp;
			}
			stk[++tp]=p[i];
		}
		for(int i=1;i<tp;++i)
			add(stk[i],stk[i+1]),add(stk[i+1],stk[i]);
		gvt=0,sizgvt=1e9,blk=pc,DFS_gvt(stk[1],0),DFS(gvt);
		for(int i=1;i<=tu;++i)
			isq[usd[i]]=false,vis[usd[i]]=false,h[usd[i]]=0;
		idx=1,tu=0;
		printf("%lld %d %d\n",ans,ansl,ansr);
	}
	return 0;
}

（注：MAXN 开到 $2\times 10^6+7$ 了之后还是相同的结果。）