题目链接：https://www.luogu.com.cn/problem/P2495

题面：

分析&做法

弱化版模板题，简单说（给我自己看的）

• 容易相处状态转移但是由于边和点太多会TLE
• 突破口：关键点总和不是很大
• 建立虚树把有用的点（所有关键点和他们之间任意两点的LCA）重新建一棵树，DP结果不会受影响
• 建立虚树的过程是用栈维护一个树上的最右链，类似单调栈（栈中元素dfn由上到下递减）
• 枚举每加入一个关键点$now$，记$lca = LCA(s[top], now)$，分为四种情况讨论（懒得放图）：

1. $lca == s[top]$：说明新加入的点在原来的最右链上，直接入栈。（否则不在原来的最右链上）
2. $dep[s[top - 1]] $$< $$dep[lca]$$且$$dep[lca] $$<$$ dep[s[top]]$：说明$lca$在链最右链最靠下面的点上面，倒数第二靠下的点的下面，连$lca -> s[top]$，$s[top]$出栈，$now$入栈
3. $dep[lca] == dep[s[top - 1]]$：和上面的差不多，只不过$lca$不用入栈了
4. 剩下的情况，说明$lca$在最右链最下面的两个点的上面，连接最下面的两点（就是栈顶和栈顶下面的点，注意要从栈顶下面的点连向栈顶），栈顶出栈，如此反复，直到出现前三种情况才加入now

代码

#include 
#include 
#include 
#include 
#define min(a, b) ((a)<(b)?(a):(b))
#define Re register
#define LL long long
#define INF 1e18 
using namespace std;

const int maxN = 2500005;

int N, M, p[maxN];

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

struct Edge {
    int pre, to, nxt, dis;
}e[maxN << 1]; int cnte = 1, head[maxN];
inline void add_Edge(int i, int j, int k) {
    e[++cnte].dis = k, e[cnte].nxt = head[i], e[cnte].to = j, head[i] = cnte;
}

int dfn[maxN];
bool cmp(int x, int y) {return dfn[x] < dfn[y];}

void Init() {
    N = read();
    for(Re int i = 1; i < N; ++i) {
        Re int u, v, w;
        u = read(), v = read(), w = read();
        add_Edge(u, v, w), add_Edge(v, u, w);
    }
    M = read();
}

int dep[maxN], fa[maxN][25], cnt;
LL mn[maxN];

void dfs(int u, int dad) {
    dfn[u] = ++cnt,
    dep[u] = dep[dad] + 1,
    fa[u][0] = dad;
    for(Re int i = head[u]; i; i = e[i].nxt) {
        Re int v = e[i].to;
        if(v == dad) continue;
        mn[v] = min(mn[u], e[i].dis),
        dfs(v, u);
    }
}

int LCA(int x, int y) {
    if(dep[x] < dep[y]) x^=y^=x^=y;
    for(int i = 20; i >= 0; --i) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if(x == y) return x;
    for(int i = 20; i >= 0; --i) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

void Pre() {
    mn[1] = INF, dfs(1, 0);
    for(int i = 1; i <= 21; ++i) {
        for(int u = 1; u <= N; ++u) {
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
        }
    }
}

int s[maxN], top;
LL f[maxN];
void DP(int u) {
    for(Re int i = head[u]; i; i = e[i].nxt) {
        Re int v = e[i].to;
        DP(v), f[u] += f[v],
        f[v] = 0;
    }
    if(!f[u]) f[u] = mn[u];
    else f[u] = min(f[u], mn[u]);
    head[u] = 0;
}
void Solve() {
    memset(head, 0, sizeof(head)),
    memset(e, 0, sizeof(e)), cnte = 0;
    while(M--) {
        int k = read();
        for(Re int i = 1; i <= k; ++i) p[i] = read();
        sort(p + 1, p + k + 1, cmp);
        int tmp = 0;
        p[++tmp] = p[1];
        for(Re int i = 2; i <= k; ++i) {
            if(LCA(p[i], p[tmp]) == p[tmp]) continue;
            p[++tmp] = p[i];
        }
        k = tmp, s[top = 1] = 1;
        for(Re int i = 1; i <= k; ++i) {
            Re int lca = LCA(s[top], p[i]);
            while(true) {
                if(lca == s[top]) {
                    s[++top] = p[i];
                    break;
                }
                if(dep[s[top - 1]] < dep[lca] && dep[lca] < dep[s[top]]) {
                    add_Edge(lca, s[top], 1), s[top] = lca, s[++top] = p[i];
                    break;
                }
                if(dep[s[top - 1]] == dep[lca] && s[top - 1] == lca) {
                    add_Edge(lca, s[top], 1), s[top] = p[i];
                    break;
                }
                add_Edge(s[top - 1], s[top], 1), top--;
            }       
        }
        while(--top) add_Edge(s[top], s[top + 1], 1);
        f[1] = 0, DP(1);
        printf("%lld\n", f[1]);
    }
}

int main() {
    Init();    
    Pre();
    Solve();
    return 0;
}