二楼放代码是个好习惯
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int kMaxN = 500000 + 10;
const int kMaxLog = 22;
const int kInf = 2000000000;
struct Graph {
struct Arc {
int to, dis;
};
vector<Arc> arcs[kMaxN];
void Add(int u, int v, int dis) {
arcs[u].push_back((Arc) {v, dis});
arcs[v].push_back((Arc) {u, dis});
}
};
Graph G; // orig. tree
int dfn[kMaxN], dfn_cnt;
int fa[kMaxN][kMaxLog], min_val[kMaxN][kMaxLog];
int depth[kMaxN];
void Dfs(int u, int f) {
depth[u] = depth[f] + 1;
dfn[u] = ++dfn_cnt;
for (int i = 1; i <= 20; i++) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
min_val[u][i] = min(min_val[u][i - 1], min_val[fa[u][i - 1]][i - 1]);
}
for (int i = 0; i < G.arcs[u].size(); i++) {
Graph::Arc& arc = G.arcs[u][i];
int v = arc.to;
if (v != f) {
fa[v][0] = u;
min_val[v][0] = arc.dis;
Dfs(v, u);
}
}
}
int GetLca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int i = 20; i >= 0; i--) {
if (depth[fa[u][i]] >= depth[v]) u = fa[u][i];
}
if (u == v) return u;
for (int i = 20; i >= 0; i--) {
if (fa[u][i] != fa[v][i]) {
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
int GetMin(int u, int v) {
int ans = kInf;
if (depth[u] < depth[v]) swap(u, v);
for (int i = 20; i >= 0; i--) {
if (depth[fa[u][i]] >= depth[v]) {
ans = min(ans, min_val[u][i]);
u = fa[u][i];
}
}
if (u == v) return ans;
for (int i = 20; i >= 0; i--) {
if (fa[u][i] != fa[v][i]) {
ans = min(ans, min_val[u][i]);
ans = min(ans, min_val[v][i]);
u = fa[u][i];
v = fa[v][i];
}
}
return min(ans, min_val[u][0]);
}
int n, m;
int k, h[kMaxN];
bool is_h[kMaxN];
bool comp(int a, int b) {
return dfn[a] < dfn[b];
}
Graph T; // virtual tree
int sta[kMaxN], top;
int GetAns(int u, int f) {
int ans = 0;
for (int i = 0; i < T.arcs[u].size(); i++) {
Graph::Arc& arc = T.arcs[u][i];
int v = arc.to;
if (v != f) {
int a = GetAns(v, u);
if (is_h[v]) {
ans += arc.dis;
is_h[v] = false;
} else {
ans += min(arc.dis, a);
}
}
}
T.arcs[u].clear();
return ans;
}
void Link(int u, int v) {
T.Add(u, v, GetMin(u, v));
}
void PrintStack() {
printf("Stack: ");
for (int i = 1; i <= top; i++) {
printf("%lld ", sta[i]);
}
printf("\n");
}
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n - 1; i++) {
int u, v, dis;
scanf("%lld %lld %lld", &u, &v, &dis);
G.Add(u, v, dis);
}
Dfs(1, 0);
scanf("%lld", &m);
for (int i = 1; i <= m; i++) {
scanf("%lld", &k);
for (int j = 1; j <= k; j++) {
scanf("%lld", &h[j]);
is_h[h[j]] = true;
}
sort(h + 1, h + k + 1, comp);
sta[top = 1] = 1;
for (int j = 1; j <= k; j++) {
if (top == 1) {
sta[++top] = h[j];
} else {
int lca = GetLca(h[j], sta[top]);
while (dfn[sta[top]] > dfn[lca]) {
if (dfn[sta[top - 1]] >= dfn[lca]) {
Link(sta[top - 1], sta[top]);
top--;
} else {
Link(lca, sta[top]);
sta[top] = lca;
}
}
sta[++top] = h[j];
}
}
while (--top) Link(sta[top], sta[top + 1]);
printf("%lld\n", GetAns(1, 0));
}
return 0;
}
```
by longlongzhu123 @ 2019-02-16 13:13:12
`#define int long long`
不是一个好习惯
by skip2004 @ 2019-02-16 13:28:21
+1
等你被卡常就知错了
by SSerxhs @ 2019-02-16 13:38:54
@[longlongzhu123](/space/show?uid=57525)
O(3)
by Smile_Cindy @ 2019-02-16 13:47:23
@[longlongzhu123](/space/show?uid=57525) int的运算速度比long long快4倍。。。
by 龙之吻—水货 @ 2019-02-16 14:12:59
@[longlongzhu123](/space/show?uid=57525) 如果真要再提高一点速度，考虑用ST表rmq求lca（$O(1)$回答），这样建虚树复杂度是$O(k)$的
我觉得#define int long long是很没水平的体现。那么多高级的算法程序你都能搞明白，难道连哪里用int哪里用long long都搞不清吗...
by GKxx @ 2019-02-16 14:13:17
嫌慢的话,写树剖吧
by command_block @ 2019-03-09 20:29:16