虚树学习总结

虚树学习总结

问题引入: 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#define N 250050#define inf 1000000000000000#define LL long longusing 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 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 1) Add(s[top-1], s[top]), top--; cout << calc(s[1]) << "\n"; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。