学习了一下重构树。 题目背景 本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个 $ n$ 个节点、 $ m$ 条边的无向连通图(节点的编号从 $ 1$ 至 $ n$)。我...
dfs序
最近公共祖先 题解【dfs序】【线段树】
煞笔题考场上没看出来……打了跟正解很接近的暴力… 题目描述 给定一棵\(n\)个节点的有根树,节点编号为\(1\sim n\),其中根节点为\(1\)号节点。每个节点都对应着一种颜色(黑/白)和一个固...
[2018.10雅礼] Equation 题解【树状数组】【dfs序】【树上差分】
感觉这个题最棘手的是树状数组部分……(前提是想到正解 题目描述 有一棵\(n\)个点的以\(1\)为根的树,以及\(n\)个整数变量\(x_i\)。树上\(i\)的父亲是\(f_i\),每条边\((i,f_i)\)有一个权...
牛客 172C 保护 题解【线段树合并】【LCA】【dfs序】
差点爆空间+时间= =好刺激啊……不过这个题的做法好清奇…… 题目描述 C国有\(n\)个城市,城市间通过一个树形结构形成一个连通图。城市编号为\(1\)到\(n\),其中\(1\)号城市为首都。国家...
洛谷 P2414 [NOI2011]阿狸的打字机 题解【AC自动机】【树状数组】【dfs序】
这一题是对AC自动机的充分理解和树dfs序的巧妙运用。 题目背景 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。 题目描述 打字机上只有28个按键,分别印有26个小写英文...