2018-01-13

虚树

本质

将询问节点建到另一棵树上，维护在原树中节点构成链上的信息，降低节点访问量。

比如如果我们当前询问一条链上的两个端点，原本如果做dfs的话复杂度是 $O(n)$ 的，但是如果是虚树，那么树上就只会有这两个端点。

建树

一般除了用到题目所要求的关节点，还需要用到关节点的 $lca$ ,但是 $lca$ 个数也是 $n^{2}$ 。考虑如何降低？？？

考虑把关节点根据 $dfn$ 值排序，比如说有三个点 $a,b,c$ ,则显然 $lca(b,c)$ 一定在 $lca(a,b)$ 和 $lca(b,c)$ 中。

树上 $k$ 个点的 $lca$ 不会超过 $k-1$ 个。

有了这个结论之后，我们相当于维护一个单调栈，如果栈为空，直接加点，否则我们看栈顶的点是不是当前点的祖先，如果不是，那么弹出栈顶继续，否则就可以把当前点加进栈了（然后从栈顶向这个点连一条边）。弹出的点一定不可能是后来点的 $lca$。

题目

传送门
裸体直接建树即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 10;
typedef long long LL;
struct edge{
	int to, w;
	edge (int _to = 0, int _w = 0) {
		to = _to, w = _w;
	}
};
vector<edge>G[maxn], E[maxn];
stack<int>chain;
int dfn[maxn], cnt, node[maxn], key[maxn];
int fa[maxn][25], mini[maxn][25], deep[maxn];
map<int,int>mp;
inline void dfs(int k, int f){
	dfn[k] = ++cnt;
	for(int i = 1; i <= 23; i++){
		fa[k][i] = fa[fa[k][i-1]][i-1];
		mini[k][i] = min(mini[k][i-1], mini[fa[k][i-1]][i-1]);
	}
	for(int i = 0; i < G[k].size(); i++){
		int kk = G[k][i].to;
		if(kk == f)continue;
		fa[kk][0] = k;
		mini[kk][0] = G[k][i].w;
		deep[kk] = deep[k] + 1;
		dfs(kk, k);
	}
}
inline bool cmp(int x, int y) {
	return dfn[x] < dfn[y];
}
inline int lca(int x, int y) {
	if(deep[x] < deep[y]) swap(x, y);
	int dt = deep[x] - deep[y];
	while (dt) {
		x = fa[x][mp[dt & -dt]];
		dt -= dt & -dt;
	} if (x == y)return x;
	for (int i = 23 ; ~i; i--)
		if(fa[x][i] != fa[y][i])
			x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}
inline int ask(int x, int y) {
	if (deep[x] < deep[y])swap(x, y);
	int dt = deep[x] - deep[y];
	int rtn = 1e9;
	while(dt) {
		int k = mp[dt & -dt];
		rtn = min(rtn, mini[x][k]);
		x = fa[x][k], dt -= dt & (-dt);
	}return rtn;
}
const LL inf = 1e15;
bool val[maxn];
inline LL calc(int k, int f) {
	LL ans = 0;
	for(int i = 0; i < E[k].size(); i++) {
		int kk = E[k][i].to; if(kk == f)continue;
		if (val[node[kk]]) ans += E[k][i].w;
		else ans += min((LL)E[k][i].w, calc(kk, k));
	}return ans;
}
LL deal() {
	sort(node + 1, node + 1 + node[0], cmp);
	node[0] = unique(node + 1, node + 1 + node[0]) - node - 1;
	int n = node[0]; key[0] = 0;
	for(int i = 2; i <= n; i++){
		int w = lca(node[i], node[i - 1]);
		node[++node[0]] = w;
		val[node[i]] = true, key[++key[0]] = node[i];
	}
	val[node[1]] = true, key[++key[0]] = node[1];
	sort(node + 1, node + 1 + node[0], cmp);
	node[0] = unique(node + 1, node + 1 + node[0]) - node - 1;
	while(chain.size())chain.pop(); int root;
	for(int i = 1; i <= node[0]; i++){
		E[i].clear();
		if(!chain.size())chain.push(i), root = i;
		else {
			int k = node[i], kk = node[chain.top()];
			while (lca(k, kk) != kk)
				chain.pop(), kk = node[chain.top()]; 
			int w = ask(k, kk);
			E[i].push_back(edge(chain.top(), w));
			E[chain.top()].push_back(edge(i, w));
			chain.push(i);
		}
	}
	LL ans = calc(root, 0);
	for(int i = key[0]; i; i--)val[key[i]] = false;
	return ans;
}
int main(){
#ifdef YSW 
	freopen("data.in", "r", stdin);
#endif
	int n; scanf("%d", &n);
	for (int i = 0; 1 << i <= n; i++) mp[1 << i] = i;
	for (int i = 1; i < n; i++){
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		G[x].push_back(edge(y, z));
		G[y].push_back(edge(x, z));
	} 
	dfs(1, 0);
	int m; scanf("%d", &m);
	while (m--) {
		int k; scanf("%d", &k);
		node[0] = 0; int x;
		while (k--)
			scanf("%d", &x), node[++node[0]] = x;
		node[++node[0]] = 1;
		printf("%lld\n", deal());
	}
	return 0;
}