【学习记录】24.02.17 树上问题 + 数据结构

KSCD_ · 2024-02-17 09:38:07 · 个人记录

树上问题/数据结构

树链剖分/树上差分

CF383C Propagating tree

分成深度为奇数和偶数两种点，对每一种点开线段树维护。

题解看到的更优做法：用 一个树状数组维护，对于深度为奇数和偶数分别加减，最后输出时也分别改为正负。

BZOJ3306 树

没听。

P3128 [USACO15DEC] Max Flow P

树上差分，树上路径加 1 转化为两端点各加 1，LCA和LCA的父亲减 1 即可。

P2680 [NOIP2015 提高组] 运输计划

最大值最小，采用二分，把最优性问题转化为可行性问题。

P4216 [SCOI2015] 情报传递

先将在 i 时刻大于 c 转化为在 i-c 时刻大于 0 ，考虑离线做法。

先读入所有询问，均转化为某时刻大于 0 的点数，转化为单点修改+路径和，由于路径和可以用点到根的路径和计算，通过dfs序可转化为单点修改+前缀和，树状数组维护即可。

若强制在线，需要可持久化数据结构，不管了。

P5838 [USACO19DEC] Milk Visits G

转化为求路径上有多少等于 C 的点，则只需要求点到根路径上有多少等于 C 的点。

考虑离线做法，把询问按 C 排序，每次将 T_i=C 的点先变为 1，用dfs序和树状数组维护 dis 数组，用树上差分求解，最后再把这些点变回 0，复杂度均摊可过。

• 以上两道题都用到了子树的dfs序连续，可以用树状数组维护。感谢学长

  HDU5692 shacks

  没听。

  P4211 [LNOI2014] LCA

  先考虑到差分的优化，转化为 1 到两点的前缀和之差。

后边没听（其实是听到一半跟不上了）。

CF696E ...Wait for it...

紫题放弃了。

P4219 [BJOI2014] 大融合

离线，先建出完整的树，给每条边一个标记，表示这条边是否存在，则原加边操作变为把一条边的 0 变为 1，修改后要修改这条边到最远的连通祖先所有点的子树大小，此处用并查集维护最远祖先，后边好像还需要用到上边的dfs序，但我听不懂了。

CF536E Tavas on the Path

离线操作，将询问按 l 排序，每次把应为 1 的点修改好后求这段路径的解。

可以树剖做，转化成区间查询，因此需要单点修改，用线段树维护答案。

可持久化数据结构

• 部分可持久化：可查询不可修改。

• 完全可持久化：可修改历史版本。

  P3919 【模板】可持久化线段树 1（可持久化数组）

  板子题，用路径复制思想，每次只把修改的版本建新节点，其他的连向上一个版本即可。

若线段树中有标记下放时，必须要重建后再下放。

P3834 【模板】可持久化线段树 2

维护序列每个前缀对所有数值的桶数组，每个前缀对应一个线段树，则第 i 个线段树为第 (i-1) 个线段树单点修改得到，用可持久化线段树维护，二分求解，也可以线段树二分，每次在两个线段树上同时向下跳，最后查找到叶节点。

P4592 [TJOI2018] 异或

可持久化01Trie树，放弃了，题解里说P4734、P2633是前置知识紫题太难了。

P3567 [POI2014] KUR-Couriers

如P3834一样建树，进行线段树二分，向下查找即可。

P2839 [国家集训队] middle

二分求解，放弃没听。

CF464E The Classic Problem

可持久化线段树和最短路结合的黑题？放弃放弃。

P3402 可持久化并查集

要完全可持久化，需要用复杂度均摊的按秩合并来做。

P3302 [SDOI2013] 森林

前置的可持久化并查集还没整明白，不听了。

LOJ6144 [2017 山东三轮集训 Day6] C

没听。