树学竞赛——NOIP历年树题刷题计划

开了个新坑。。12月NOIP之前争取填完吧。。

目前还剩：P5659 P5024（这两个阴间题目不打算做了，所以算是填完坑了吧）

P5658 括号树

先考虑一条链的情况。

发现这玩意可以 $\operatorname{O}(n)$ 转移。

然后推广到一棵树上就行了（

转移的细节要考虑一下，然后就没了。

时间复杂度 $\operatorname{O}(n)$ 。

---

P5666 树的重心

一道树上倍增+换根的好题。

首先有一个显而易见的结论就是：一棵树的重心必定在这棵树根节点往下的重链上。

那么就可以倍增跳重链了。

dfs 一棵树，考虑删边情况。

删边之后，那个子树很好处理，但是子树以外的部分需要换根解决，讨论即可。

时间复杂度 $\operatorname{O}(n\log n)$。

（貌似有 $\operatorname{O}(n)$ 做法？

---

P5021 赛道修建

看了题，一眼就是二分。

考虑二分这个长度最小的赛道的值，那么题目变成了“能否修建 $m$ 条以上的赛道使得这几条赛道的长度都 $\ge x$ ”。

可以一遍 dfs 解决。

具体来说：对于每个点，它往下可以有若干条没用过的链，那么可以两两拼起来，拼的方式跟P1094差不多。就是一个爆了，就让它自己待着；否则就两两拼，并且小的和大的拼。拼完之后多余的（太小了或者拼完了剩下了）就取个最大值了返回，在处理父亲节点的时候有用。

这个拼的过程可以用 multiset 维护，总时间复杂度 $\operatorname{O}(n\log^2n)$。

（话说我 #8 被卡T了，吸了氧才过

---

P2680 运输计划

一眼二分题。

二分完了，来一波树上差分随便搞搞。

具体来说：二分一个 $mid$ 表示这个答案要求的最短时间，然后找一遍所有路径中超出要求的，做个差分，找到所有这些路径中都经过的一些边，枚举这些边看看有没有一条边能使得这些路径长度都 $\le mid$ 。

时间复杂度 $\operatorname{O}(n\log \sum t_i+m\log n)$

---

P1351 联合权值

由于要求的点对之间距离为 $2$，于是考虑枚举点对之间的中转点。

对于每个中转点 $u$，它带来的点对的联合权值之和就是 $2$ 倍的所有与它相连的点两两配对的权值乘积之和。

也就是 $\sum_{(u,v)\in E}\sum_{(u,w)\in E, w\not =v}W_vW_w$。

这玩意可以通过完全平方公式转化成：$(\sum_{(u,v)\in E} W_v)^2-\sum_{(u,v)\in E} W_v^2$ 。

扫一遍每个点为中转点的情况，最后求和即可。

关于最大值就对于每个中转点找两个 $W$ 最大的点求联合权值，最后取 $\max$ 即可。

可以 $\operatorname{O}(n)$ 解决。

---

P1099 树网的核

$\operatorname{O}(n^3)$ 暴力随便艹过去。。

先 floyd 一下，然后随便暴力枚举就过了。。。

---

P7073 表达式

众所周知，后缀表达式可以 $\operatorname{O}(n)$ 用一个栈求解，而且可以建一棵树。

那么可以把题目中的后缀表达式先建一个树出来，算出每个点子树的答案。

接着对于每个点 $i$ 考虑一下改变它会不会影响上面它父亲节点的结果，可以根据之前算出的答案以及它父亲的运算符来求。开一个 bool 数组记为 $can_i$。

那么对于每一个 $x_i$，如果从根节点到它的路径上所有点的 $can$ 值都为 $1$ 的话，那么改变 $x_i$ 就会改变最终结果。否则不会改变最终结果。具体实现可以对每一条根节点到叶子节点的路径都做一个 $can$ 的前缀和来解决。

时间复杂度 $\operatorname{O}(n+q)$。

---

P5689 多叉堆

算是一个树（森林？）题吧。

其实是 树 数学题。

用并查集维护每个树根，然后对于每棵树，令 $ans_i$ 表示以 $i$ 为根的树的答案，$sz_i$ 表示以 $i$ 为根的树的大小。

那么当把以 $x$ 为根的树插进以 $y$ 为根的树中时，$ans_y=ans_y\times ans_x\times\operatorname{C}_{sz_y+sz_x-1}^{sz_x}$。然后更新 $sz_y=sz_y+sz_x$。

对于组合数，可以预处理阶乘和阶乘的逆元来算。利用公式 $C_m^n=\frac{m!}{n!(m-n)!}$ 求解。

---

P1600 天天爱跑步

神仙树上差分题。

这是几个月之前做的。详细见我的题解

---

P1967 货车运输

这题是好久好久之前写的呢。

一句话题解：在最大生成树上跑 $\operatorname{lca}$。

没啥好说的。

---

P1084 疫情控制

可以推出一个显而易见的结论：军队一定要往上移动。

而且时间这个东西可以二分。

那么问题变成：在规定时间内，能不能控制疫情？

首先尽可能把军队往上移，然后看看能不能移到 $1$ 这个点。

如果不行，那么就让它留在这里。

如果可以的话，分以下情况讨论：

1. 能到 $1$ 号节点但是回不来了：还不如就让它呆在这里呢
2. 能去别的节点：把所有的需要军队的根节点的叶子节点求出来，然后把它们到根的距离开一个数组存。再把能去别的节点的所有军队的剩余时间都存进另一个数组，跑个双指针，就做完了。

---

完结撒花✿✿ヽ(°▽°)ノ✿