算法思想

一些树上的问题，树的节点个数比较多，但是每次询问涉及到的点却不多，这个时候可以把这 $k$ 个节点提出来新建一棵树，这样复杂度就只和 $k$ 相关。

算法流程

用一个栈来维护从当前虚树根到当前节点这一条链，先把所有节点按 $dfs$ 序排序，对于新加进来的这个点 $v$ ，求出他和栈顶元素的 $LCA$ ，设为 $lca$ ，首先如果 $lca=s[top]$ ，那么说明 $lca$ 是 $s[top]$ 的子节点，直接把 $v$ 压栈，跳过这个过程，否则把他和栈中的第二个元素（不是第一个）比较 $dfs$ 序，如果 $dfn[lca]<dfn[s[top-1]]$ ，那么这时说明 $lca$ 在 $s[top-1]$ 到根这一条链上，也就说明 $s[top-1]$ 这一棵子树已经处理完毕，把 $s[top]$ 和 $s[top-1]$ 连边并把 $s[top]$ 弹掉，一直这样做下去，因为最后栈一定不空，所以会产生两种情况：栈中只剩一个元素或者 $dfn[lca]\geqslant dfn[s[top-1]]$ ，如果是第二种情况，那么连边 $s[top]\longleftrightarrow lca$ ，因为 $lca$ 一定是 $s[top]$ 的祖先，而又是栈中第二个节点的子节点，所以一定是父亲，那么把 $s[top]$ 弹栈，这个时候再把 $lca$ 和 $v$ 压栈，注意如果相同就不进行这个操作，这样会剩一条链，把他们依次连过去即可。最后的栈底就是虚树的根。这样就得到了只包含关键点和他们的 $LCA$ 的一棵树，本质是一个模拟 $dfs$ 的过程。

HEOI大工程

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 1000010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int fa[MAXN],dep[MAXN],top[MAXN],son[MAXN],siz[MAXN];

int dfn[MAXN],tot = 0;

#define R register

void dfs1(int k,int depth)

{

	dfn[k] = ++tot;

	dep[k] = depth;

	siz[k] = 1;

	for(R int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(R int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

inline int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

int v[MAXN];

vector<int> g[MAXN];

bool cmp_dfn(int a,int b){return dfn[a] < dfn[b];}

int s[MAXN],tp = 0;

typedef long long ll;

ll ans1,ans2,ans3;

ll f1[MAXN],f2[MAXN];

bool tag[MAXN];

int dp(int k)

{

	R int siz = 0;

	if(tag[k])siz = 1;

	f2[k] = 0x3f3f3f3f;

	if(tag[k])f2[k] = 0;

	f1[k] = 0;

	for(R vector<int>::iterator i = g[k].begin();i != g[k].end();++i)

	{

		R int sson = dp(*i);

		siz += sson;

		ans1 += 1ll * (dep[*i] - dep[k]) * (v[0] - sson) * sson;

		ans2 = min(ans2,f2[k] + f2[*i] + dep[*i] - dep[k]);

		f2[k] = min(f2[k],f2[*i] + dep[*i] - dep[k]);

		ans3 = max(ans3,f1[k] + f1[*i] + dep[*i] - dep[k]);

		f1[k] = max(f1[k],f1[*i] + dep[*i] - dep[k]);

	}

	g[k].clear();

	return siz;

}

int main()

{

	scanf("%d",&n);

	for(R int i = 1;i < n;++i)add(rd(),rd());

	dfs1(1,1);dfs2(1,1);

	scanf("%d",&m);

	while(m--)

	{

		v[0] = rd();

		for(R int i = 1;i <= v[0];++i)v[i] = rd();

		sort(v + 1,v + 1 + v[0],cmp_dfn);

		tp = 0;s[++tp] = v[1];

		for(R int i = 1;i <= v[0];++i)tag[v[i]] = true;

		for(R int i = 2;i <= v[0];++i)

		{

			if(v[i] == v[i - 1])continue;

			R int lca = LCA(s[tp],v[i]);

			if(lca == s[tp])

			{

				s[++tp] = v[i];

				continue;

			}

			while(tp >= 2)

			{

				if(dfn[lca] < dfn[s[tp - 1]])

				{

					g[s[tp - 1]].push_back(s[tp]);

					--tp;

				}

				else

				{

					g[lca].push_back(s[tp]);

					--tp;

					break;

				}

			}

			if(tp == 1 && dfn[lca] < dfn[s[tp]])

			{

				g[lca].push_back(s[tp]);

				s[tp] = lca;

			}

			if(lca != s[tp])s[++tp] = lca;

			s[++tp] = v[i];

		}

		while(tp >= 2)

		{

			g[s[tp - 1]].push_back(s[tp]);

			--tp;

		}

		ans1 = 0;ans2 = 0x3f3f3f3f3f3f3f3f;ans3 = 0xc0c0c0c0c0c0c0c0;

		dp(s[tp]);

		printf("%lld %lld %lld\n",ans1,ans2,ans3);

		for(int i = 1;i <= v[0];++i)tag[v[i]] = false;

	}

	return 0;

}