题意略（太复杂了不想写）题解令 $f[i]$ 为不大于 $x$ 的最大斐波那契数，那么 $x$ 的父亲节点就是 $x-f[i]$ 。斐波那契数列的第 $58$ 项刚好小于 $10^{12}$ ，所以预处理前 $58$ 个就行了。求两个节点的 $\text{LCA}$ 可以用一种类似树剖的方法，不断地取 $u$ 和 $v$ 中的较大值跳到父节点，直到 $u$ 和 $v$ 相等。层数最多只有 $...
题意有一棵 $n(\le 3\times 10^5)$ 个点的树和 $m(\le 3\times 10^5)$ 条路径，可以把一条边的边权改为 $0$ ，求所有路径长度最大值的最小值。题解求最大的最小值，可以二分答案 $mid$ 。可以发现如果路径的长度 $> mid$ ，那么路径上一定有一条边要被修改。所以修改的这条边需要覆盖所有长度 $> mid$ 的路径，并且边权要 $\g...
题意有一棵 $N$ 点的树，有 $Q$ 次询问 $(a,b,c,d)$ ，问 $a\rightarrow b$ 与 $c\rightarrow d$ 是否相交。$N,Q\le 100000$ 。题解可以发现两条边相交，就一定存在一条边的最高点在另一条边上，即端点的 $\text{LCA}$ 。所以只用求 $\text{LCA}$ 就行了。第一次写倍增 $\text{LCA}$ ，感觉还是树剖...
题意给一棵有 $n$ 个节点的树，然后再连 $m$ 条不重合的附加边，可以删除一条树边和一条附加边，问有多少种删除方法可以使树断裂。题解显然，每次加一条边以后树上一定会形成环，这个环任意断附加边就可以形成树，而树上任意断一条边就可以使树断裂。但是有可能会形成很多有重叠部分的环，这样按照上述方法不一定可以让树断裂。所以我们可以对每一条树边 $i$ 记录包含它的环的个数 $f[i]$ ，然后进行...