算法学习 / 树上问题
a minute read (About 187 words)

虚树

概述

在处理某些树上问题时，并非树上的所有节点都起作用；这时可以借助虚树，将树上重要的点构造成一棵树，在虚树上处理问题，优化时间复杂度。

模板

用栈来维护虚树上的一条从根到 $u$ 的链。如果 $u$ 是栈顶节点的儿子，则入栈；否则将栈中 dfn 值大于 $\text{lca}(u,s.top())$ 的元素出栈。

伪代码
1
2
3
4
5
6
7
8
9
10
11
将树上所有关键点按照 dfs 序排序
stack.push(1)
for u = 1 ~ n: //假设当前正在处理节点 u
	lca = Lca(u, stack.top())
	while stack.top() != lca:
		tmp = stack.top()
		stack.pop()
		if (dfn[stack.top()] < dfn[lca]):
			stack.push(lca)
		AddEdge(stack.top(), tmp)
	stack.push(u)
# 虚树
题解-luogu-p4103大工程
2019-10-1 国庆节

Comments

Follow

一言（ヒトコト）


    2333



Recent

Categories

Tag Cloud

0/1分数规划 2-SAT FFT/NTT KMP Pólya计数 ST算法 bitset dfs序 python set 主席树 乘法逆元 二分图 二分图匹配 二分答案 二叉堆 二维偏序 倍增 分块 前缀和 动态点分治 动态规划 单调队列 博弈论 卡特兰数 可持久化trie 后缀自动机 启发式合并 哈希(hash) 堆 复杂度分析 多项式 字符串 容斥原理 差分 差分约束系统 平衡树 异或 强连通分量 排序 搜索 数学 数学期望 数据结构 数论 最小割 最短路 最短路树 最近公共祖先 构造 栈 树上前缀和 树上差分 树套树 树形dp 树状数组 树链剖分 概率 欧拉函数 欧拉路 点分治 状态压缩 生成函数 生成树 矩阵 离散化 素数 线性基 线段树 组合数 组合计数 网络流 群论 背包 虚树 行列式 计数dp 计算几何 贪心 费用流 逆元 高斯消元
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×