前言
在整理总结题解的时候突然发现倍增这一章竟然连题解都没有写过，直接晕厥
T1：
直接做
T2：
首先根据倍增思想，现预处理出开 \(2^j\) 次车，A/B先开车所到达的地点，和开的距离
这样两种查询，都可以根据预处理的来倍增求出
然后如何预处理呢？
我们维护一个链表，链表开始是所有城市按照高度排完序后的顺序，因为有条件说距离最近的一定是下标比它大的城市，所以我们下标从小向大枚举，如果已经遍历过了就从链表中删除该城市，然后找到这个城市前两项和后两项来统计距离最近，次近城市的位置
T3：
很巧妙的一道floyd题，我们先预处理出所有距离为 \(2^t\) 的任意两点，设数组 \(dp[i][j][t]=1\) 表示在i，j中存在一条走 \(2^t\) 的路径，再将所有i，j为1的两点重新建图，边长为1，否则为无穷大，再跑一遍floyd即可
T4：
我们可以发现，一条边有且仅能到达唯一的目的地，所以倍增求一下每个点经过指数条边权值和和最小值即可
T5：
首先设 \(dp[u]\) 表示 想要从u走到首都需要的最小花费
所以有状转方程： 对于一种车票（v是u的祖先）
\[dp[u]=\min\{dp[v]+w_i\}(dep[u]-dep[v]<=k_i) \]然后我们可用倍增求出最小的 \(dp[v]\)
标签：链表,题解,城市,问题,倍增,预处理,dp From： https://www.cnblogs.com/zcxnb/p/18678429