洛谷官方题单 【图论2-1】树 部分题解
说实话这个题单质量真的挺高的,老老实实做完大部分经典套路都会了(严重超纲的题给萌新做能不变强吗
P5908 猫猫和企鹅
简单dfs
|
P1099 [NOIP2007 提高组] 树网的核
给定一颗无根带权树,找一条任意一个直径上的路径,长度不超过 $s$,使得其余的点到该路径的距离的最大值最小
点 $u$ 到路径 $p$ 的距离为 $\min_{v\in p}{d(u,v)}$
- solution
考虑多条直径,必然相交于同一点
并且我们只需要在一条直径上求最小偏心距即可
一看数据 $N\le 300$,差点没绷住😅,但是也在情理之中,一开始默认当成 $N\le 10^5$,还纳闷怎么07年的NOIP就这么残暴了
直接暴力 枚举一条直径上的起点,然后路径尽可能的长,dfs一遍,$O(N^2)$
|
偏心距求了一个$max$,又要求最小的偏心距,一看到最小值最大或者最大值最小就很容易往单调性上去想
考虑二分答案,那么对于直径上找出来的核,直径的两个端点为 $u,v$,核的两端,靠近 $u$ 的为 $p$,靠近 $v$ 的为 $q$
那么检查 $p,q$ 的距离是否 $\le s$,$u$ 到 $p$ 的距离和 $v$ 到 $q$ 的距离是否小于等于 $mid$ 值,以及直径外的点到核最远距离是否小于等于 $mid$
这样二分下来就是 $O(N\log{K})$ 的,但不知道为什么不吸氧交到 $N\le 3\times 10^5$ 的消防只有50分,吸了氧剩下的点勉强跑过去,hydro上的remote judge也是同样的效果
然后就是 $N\le 5\times 10^5$ 的BZOJ数据,这个我在 hydro 测的,直接MLE了
按理说C++17开O2的STL速度应该还是可以的,但是洛谷上吸了氧剩下的50分也是极限跑过,换了BZOJ数据(即hydro自测)也就快了100ms不到,在t的边缘
可能是fill常数太大了,按理说直接在直径上二分没什么复杂度。懒得换C风格的写法了。
|
考虑单调性,在上一步二分的基础上,发现不需要二分,只要枚举直径上的核的一个端点,剩下的另一个端点保持不超过 $s$ 的距离直接移动,这样复杂度是均摊 $O(N)$ 的,也叫尺取。
那么偏心距就 $\ge \max{(dis[u,p],dis[v,q])}$
然后考虑不在直径上的点到核的偏心距,如果点到直径的路径和核没有交集,那么不会比直径的两端 $u,v$ 更远,如果有交集,那么到核的距离就是到直径的距离
故最后标记完直径上的点向外dfs一遍求最大值,并且这是一个固定的值,就是偏心距的下界之一
|
P1395 会议
不知道为什么,一眼就是一个树形DP
考虑 f[i] 表示代价。从父节点 $u$ 推到 $v$,即
$$f[v]=f[u]+(n-siz[v])-siz[v]$$
$siz[u]$ 表示以 $u$ 为根的子树大小
打两遍dfs即可
|
P3379 【模板】最近公共祖先
模板题,放几种方法
最常用的方法之一
|
另一种上跳方法,更像是树形结构上的分块
没有学过树剖的左转 OI-wiki
|
考虑每个节点的dfn,从 $u$ 走到 $v$ 的过程中不会经过比 $lca(u, v)$ 深度更小的节点
然后做一个区间查询最小值就行了