「HEOI2014」大工程 - 虚树 + 动态规划

给你一棵$n$个点的树，有$q$次询问。

每次询问给出一个$k$，并给出一个大小为$k$的点集$S$。求这$k$个点两两所形成的$\binom{k}{2}$条路径中：

• 所有路径长度和
• 最短路径的长度
• 最长路径的长度

$n\le 10^6, (\sum k)\le 2n$

Links

Luogu P4103

LOJ 2219

Solution

显然可以构建虚树，下面考虑三个小问怎么做

1. • 显然可以考虑每条边对答案的贡献，答案就是每条边的边权乘以两端子树内关键点数目
   • 我自己做的时候没想到这个trick，于是就用了一种特别麻烦的树形dp，具体可以见代码
2. 我们可以设$f[x]$表示从$x$开始，向子树能够延伸的最短链的长度。每次遍历一遍所有儿子，求出最短链和次短链的和，对答案取min即可
3. 与2类似

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1000000 + 100;
const int inf = 0x3f3f3f3f;

int N, Q;
int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];
int fa[Maxn], dfn[Maxn], dfs_clock, son[Maxn], top[Maxn], size[Maxn], dep[Maxn];

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

inline void dfs_init (int x)
{
	dep[x] = dep[fa[x]] + 1, size[x] = 1;

	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (y == fa[x]) continue;
		fa[y] = x;
		
		dfs_init (y);
		if (size[y] > size[son[x]]) son[x] = y;
		size[x] += size[y];
	}
}

inline void dfs_init (int x, int now)
{
	dfn[x] = ++dfs_clock, top[x] = now;
	if (son[x]) dfs_init (son[x], now);

	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (y == fa[x] || y == son[x]) continue;

		dfs_init (y, y);
	}
}

inline int get_lca (int x, int y)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		x = fa[top[x]];
	}
	if (dep[x] < dep[y]) swap(x, y);
	return y;
}

int K, A[Maxn];

namespace VTREE
{
	int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1], W[Maxn << 1];
	int Stack[Maxn], top;
	int Key[Maxn];

	inline void add_edge (int x, int y, int z) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; W[e] = z; }

	inline int cmp_by_dfn (int x, int y) { return dfn[x] < dfn[y]; }

	inline void build ()
	{
		for (int i = 1; i <= K; ++i) Key[A[i]] = 1;
		sort(A + 1, A + K + 1, cmp_by_dfn);
		for (int i = K; i > 1; --i) A[++K] = get_lca (A[i], A[i - 1]); A[++K] = 1;
		sort(A + 1, A + K + 1, cmp_by_dfn);
		K = unique (A + 1, A + K + 1) - A - 1;

		for (int i = 1; i <= K; ++i)
		{
			while (top && dfn[Stack[top]] + size[Stack[top]] - 1 < dfn[A[i]]) --top;
			if (top) add_edge (Stack[top], A[i], dep[A[i]] - dep[Stack[top]]);
			Stack[++top] = A[i];
		}
	}

	LL Dp[Maxn], f[Maxn], g[Maxn]; 
	// Dp[X] : the answer of X's subtree
	// f[X] : the sum of the path from the key points in X's subtree to X
	// g[X] : the sum of the key points in X's subtree

	inline void get_dp1 (int x)
	{
		Dp[x] = f[x] = g[x] = 0;
		if (Key[x]) ++g[x];

		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];

			get_dp1 (y);

			g[x] += g[y];
			Dp[x] += Dp[y];
		}

		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];
			LL now = f[y] + g[y] * W[i];
			f[x] += now;
			Dp[x] += (g[x] - g[y]) * now;
		}
	}

	LL ans1, ans2;

	// f[x] : the length of the shortest chain in X's subtree
	// g[x] : the length of the longest chain in X's subtree

	inline void get_dp2 (int x)
	{
		f[x] = inf, g[x] = -inf;

		LL Max = -inf, Sec_Max = -inf, Min = inf, Sec_Min = inf;

		if (Key[x]) Min = Max = 0;

		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];

			get_dp2 (y);

			f[y] += W[i], g[y] += W[i];

			if (f[y] <= Min) Sec_Min = Min, Min = f[y];
			else if (f[y] <= Sec_Min) Sec_Min = f[y];

			if (g[y] >= Max) Sec_Max = Max, Max = g[y];
			else if (g[y] >= Sec_Max) Sec_Max = g[y];
		}

		f[x] = Min, g[x] = Max;
		Chkmin (ans1, Min + Sec_Min);
		Chkmax (ans2, Max + Sec_Max);
	}

	inline void solve ()
	{
		get_dp1 (1);
		printf("%lld ", Dp[1]);
		ans1 = 0x3f3f3f3f3, ans2 = -1;
		get_dp2 (1);
		printf("%lld %lld\n", ans1, ans2);
	}

	inline void init ()
	{
		for (int i = 1; i <= K; ++i) Begin[A[i]] = Key[A[i]] = 0;
		e = top = 0;
	}
}

inline void Solve ()
{
	dfs_init (1);
	dfs_init (1, 1);

	Q = read<int>();
	while (Q--)
	{
		K = read<int>();
		for (int i = 1; i <= K; ++i) A[i] = read<int>();
		VTREE :: build ();
		VTREE :: solve ();
		VTREE :: init ();
	}
}

inline void Input ()
{
	N = read<int>();
	for (int i = 1; i < N; ++i)
	{
		int x = read<int>(), y = read<int>();
		add_edge (x, y);
		add_edge (y, x);
	}
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}