本文主要是介绍虚树学习总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题引入: m个询问, 每次给出k个点, 求使这k个点都不与根连通的最小代价 ( m <= 250000, sum(k) <= 500000)
虚树: 类似有很多组询问, 而询问总点数又较小的, 可以用虚树解决, 具体来说, 就是将每次的k个点重新建一棵树, 然后在这颗树上DP
建树的方法 : 总体来说, 就是用栈维护一个根到当前点的链, 栈中的节点就是根到栈顶路上的所有关键点, 具体步骤如下
1. 将这k个点按dfs序排序, 一个一个插入
2. 如果当前点和栈顶的祖先的lca是栈顶, 说明当前点是它的子孙, 直接将它入栈
3. 否则, 则说明栈顶与当前点不在一个子树内, 就要将lca到栈顶这一段链退出去(退时两两连边), 然后将lca入栈, 当前点入栈
4. 最后将栈中剩下的最后一条链两两连边
void Insert(int x){if(top == 0){ s[++top] = x; return;} // 栈为空直接插入int l = lca(s[top], x); if(s[top] == l) {s[++top] = x; return;} // 还在当前子树, 插入该点依然保证到根是一条链while(top > 1 && dep[s[top-1]] > dep[l])
// 要把lca子树的关键点退出, 才能保证到另一棵子树栈维护的仍然是一条链 Add(s[top-1], s[top]), top--; // 退出时处理当前子树的边if(dep[l] < dep[s[top]]) Add(l, s[top]), top--;if(l != s[top]) s[++top] = l; // lca也作为关键点s[++top] = x;
}while(top > 1) Add(s[top-1], s[top]), top--; // 处理最后一条链
开头的问题也就是迎刃而解了, 只需维护点到根的最小边权
因为当一个点作为关键点时, 它的子树的关键点就没有用了, 于是在if(s[top]==l) 哪里直接return就可以了
P2495 [SDOI2011]消耗战
#include<bits/stdc++.h>
#define N 250050
#define inf 1000000000000000
#define LL long long
using namespace std;
int read(){int cnt = 0; char ch = 0;while(!isdigit(ch)) ch = getchar();while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();return cnt;
}
int first[N], nxt[N<<1], to[N<<1], w[N<<1], tot;
void add(int x,int y,int z){ nxt[++tot] = first[x], first[x] = tot;to[tot] = y, w[tot] = z;
}
int n, m, dep[N], fa[N][20], dfn[N], sign, a[N];
LL Min[N]; int s[N], top;
bool cmp(int a,int b){ return dfn[a] < dfn[b];}
void dfs(int u,int f){for(int i=1;i<=18;i++)fa[u][i] = fa[fa[u][i-1]][i-1];dfn[u] = ++sign;for(int i=first[u];i;i=nxt[i]){int t = to[i]; if(t == f) continue;dep[t] = dep[u] + 1; fa[t][0] = u;Min[t] = min(Min[u], (LL)w[i]); dfs(t, u);}
}
int lca(int x,int y){if(dep[x] < dep[y]) swap(x, y);for(int i=18;i>=0;i--)if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];if(x == y) return x;for(int i=18;i>=0;i--)if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];return fa[x][0];
}
vector<int> v[N];
void Add(int x,int y){ v[x].push_back(y);}
void Insert(int x){if(top == 0){ s[++top] = x; return;}int l = lca(s[top], x);if(l == s[top]) return;while(top > 1 && dep[s[top-1]] > dep[l]) Add(s[top-1], s[top]), top--;if(dep[s[top]] > dep[l]) Add(l, s[top]), top--;if(l != s[top]) s[++top] = l;s[++top] = x;
}
LL calc(int x){if(v[x].size() == 0) return Min[x]; LL ans = 0;for(int i=0; i<v[x].size(); i++){ans += calc(v[x][i]); } v[x].clear();return min(ans, Min[x]);
}
int main(){n = read();for(int i=1;i<n;i++){int x = read(), y = read(), z = read();add(x, y, z); add(y, x, z);} Min[1] = inf; dep[1] = 1; dfs(1, 0);m = read();while(m--){int k = read();for(int i=1;i<=k;i++) a[i] = read(); sort(a+1, a+k+1, cmp); top = 0;for(int i=1;i<=k;i++) Insert(a[i]);while(top > 1) Add(s[top-1], s[top]), top--;cout << calc(s[1]) << "\n"; } return 0;
}
这篇关于虚树学习总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
