题目链接
题解
抽离虚树dp
对于虚树我们可以O(m)构造
dfs序排序后，易证相邻两点lca为所有出现到的lca
每次维护一个深度递增的栈，用其来维护一个节点的虚树，当其被pop出栈时他的虚数也构造完了
那么栈中序列即为链的父子关系
每次若将要插入一点与栈顶点的lca，位于栈顶上个点的虚树树中，且不为栈顶点的后代<若是的话直接压入栈中，继续跟新该链>，那么弹出栈顶点后直接压入栈中，连边，否则pop到是为止，此时开始新链更新
pop时连边建立父子关系就好了
然后就是普通的树形dp
ps:我一定要出一道虚树 ~~毒瘤~~ 码农题
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
const int maxn = 2000007;
struct node {
int w,v,next;
} edge[maxn << 1],e[maxn << 1];
int num = 1,head[maxn],dfn[maxn] ;
inline void add_edge(int u,int v,int w) {
edge[++ num].v = v;edge[num].next = head[u];head[u] = num; edge[num].w = w;}
int h[maxn];
int num1 = 0;
inline void add(int u,int v) {
if(u == v) return ;
e[++ num1].v = v;e[num1].next = h[u];h[u] = num1;
}
int n,m,id = 0,dad[maxn][20],deep[maxn];LL mn[maxn];
void dfs(int x) {
dfn[x] = ++id;
deep[x] = deep[dad[x][0]] + 1;
for(int i = 0;dad[x][i];++ i) dad[x][i + 1] = dad[dad[x][i]][i];
for(int i = head[x];i;i = edge[i].next) {
int v = edge[i].v;
if(v == dad[x][0]) continue;
dad[v][0] = x;
mn[v] = std::min(mn[x],(LL)edge[i].w);
dfs(v);
}
}
int lca(int x,int y) {
if(deep[x] > deep[y]) std::swap(x,y) ;
for(int i = 18;i >= 0;-- i) if(deep[dad[y][i]] >= deep[x]) y = dad[y][i];
if(x == y) return x;
for(int i = 18;i >= 0;-- i)
if(dad[x][i] != dad[y][i]) x = dad[x][i],y = dad[y][i];
return dad[x][0];
}
int tt[maxn],stack[maxn];
inline bool cmp(int x,int y) { return dfn[x] < dfn[y]; }
LL dp[maxn];
void Dp(int x) {
dp[x] = (LL)mn[x];
LL tmp = 0;
for(int i = h[x];i;i = e[i].next) {
Dp(e[i].v);
tmp += dp[e[i].v];
}
h[x] = 0;//顺便清空
if(tmp == 0) dp[x] = (LL)mn[x];
else dp[x] = std::min(dp[x],tmp);//要么割自己，要么割子树
}
void solve(int k = 0,int top = 0,int tot = 0) {
k = read();
for(int i = 1;i <= k;++ i) tt[i] = read();
std::sort(tt + 1,tt + k + 1,cmp);
stack[++ tot] = tt[1];
for(int i = 2;i <= k;++ i)
if(lca(tt[tot],tt[i]) != tt[tot]) tt[++ tot] = tt[i];
//根据题意，切掉子树的根后子树就不用管了
stack[++ top] = 1;
for(int i = 1;i <= tot;++ i) {
int now = tt[i],f = lca(now,stack[top]);
while("tle") {
if(deep[stack[top - 1]] <= deep[f]) {
add(f,stack[top --]);
if(stack[top] != f)stack[++ top] = f;
break;
}
add(stack[top - 1],stack[top]) ;top --;
}
if(stack[top] != now)stack[++ top] = now;
}
while(-- top) add(stack[top],stack[top + 1]);
Dp(1);
printf("%lld
",dp[1]);
}
int main() {
n = read();
for(int u,v,w,i = 1;i < n;++ i) {
u = read();v = read();w = read();
add_edge(u,v,w); add_edge(v,u,w);
}
mn[1] = 10000000000000007LL;
dfs(1);
m = read();
for(int i = 1;i <= m;++ i) {
solve();
}
return 0;
}