树路径
树链剖分(Link/cut tree)
用途：
树路径信息维护
将一棵树划分成若干条链，用数据结构(线段树、treap和splay树等)去维护每条链，时间复杂度为O(n)
基本介绍：
首先定义size(X)为以X为根的子树的节点个数。
将树上每一条边都分为两类：
重边：令节点V为节点U中的儿子节点数中size值最大的节点，那么(U,V)就为一条重边
轻边：除重边外其余边
重链(重路径)：一条只包含重边的路径
对于按轻重边划分有如下两条性质：
1.对于轻边(u, v)，size(v)<=size(u)/2
2.对于从根到某一点的路径，轻边数不超过O(logn)，重链数不超过O(logn)
对性质1进行证明：
设u有k个子节点，分别为v1,v2,...，vk，设(u,v1)为重边，则其余(u,vi)(i>1)为轻边。
size(u)=size(v1)+size(v2)+...+size(vk)+1 (其中k>=2，因为若k=1,则该边必为重边，即不含轻边)
size(v1)>=size(vi)(i>1)
对于任意i s.t. 1<i<=k，有：
size(vi)+size(vi)=2*size(vi)<=size(vi)+size(v1)<=size(u)
即：size(vi)<=size(u)/2
对性质2进行证明:
设从root到v的路径中有k条轻边:root -> ... -> v1 -> ... -> v2 -> ... -> vk -> ... -> v (其中->v1,->v2,...,->vk为轻边)
size(vk)>=size(v)>=1
size(vk的前趋)>=2*size(vk)(性质1)>=2
同理可得：size(vk-1的前趋)>=2*size(vk的前趋)>=2^2
所以有：
n=size(root)>=size(v1的前趋)>=2^k
所以k=O(logn)
从root到v的路径中有k条轻边，那么路径上其他边即为重边，那么重链数=k+1，所以重链数=O(logn)。
那么从根节点出发，沿着重路径一直往下，可拉出一条重链，其他那些树上不在这条重路径上的节点可分别向下拉出一条重链(重链长度可为0,即重链只有一个节点)，那么树便可拆分为若干条重链，这样就可以套用其他数据结构(线段树等)来维护。
LCA倍增法
若只是对树上任意两点之间的路径信息进行查询，而不需要动态操作，那么不需用到上面的树链剖分，毕竟树链剖分再套用别的动态数据结构非常麻烦，那么就可用LCA(最近邻公共祖先)的倍增法实现，预处理为O(nlogn)，之后的查询操作为O(logn)。
查询树上任意两个节点之间的路径信息，实际上就是找这两个节点的LCA，因为唯一路径就是这两个节点分别到LCA会合，所以关键问题就是求LCA，需要的路径信息可在找LCA过程中维护。找LCA的思想类似于RMQ，定义anc[i][j]为节点i的第2^j个父节点，anc[i][0]就是i的父节点，anc[i][1]就为i的爷爷节点，那么就有如下递推式：anc[i][j]=anc[anc[i][j-1]][j-1]。先预处理出每个节点的深度并记录，通过不断上升节点来找到LCA。具体代码看例题。
POJ 1330: Nearest Common Ancestors
题意就是给出一颗树，再给两个节点，求这两个节点的LCA。时间复杂度为O(nlogn)。
代码如下：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;const int maxn = 10000 + 3;
int n, depth[maxn], anc[maxn][15], depth_bound, pre[maxn];
vector<int> G[maxn];inline void read(int& buf) {buf = 0;char c = getchar();while (!isdigit(c)) c = getchar();while (isdigit(c)) {buf = (buf << 3) + (buf << 1) + c - '0';c = getchar();}
}void init() {depth_bound = ceil(log(n) / log(2.0) + 0.5);for (int i = 1; i <= n; i++) {G[i].clear();depth[i] = -1;pre[i] = -1;for (int j = 0; j < depth_bound; j++) anc[i][j] = -1;}
}void dfs(int pre, int now, int dep) {depth[now] = dep;anc[now][0] = pre;int bound = G[now].size();for (int i = 0; i < bound; i++)if (pre != G[now][i]) dfs(now, G[now][i], dep + 1);
}void get_anc() {for (int j = 1; j < depth_bound; j++)for (int i = 1; i <= n; i++)if (anc[i][j - 1] != -1)anc[i][j] = anc[anc[i][j - 1]][j - 1];
}int lca(int a, int b) {if (depth[a] < depth[b]) swap(a, b);int d = depth[a] - depth[b];if (d)for (int i = 0; i < depth_bound; i++)if (d & (1 << i)) a = anc[a][i];if (a == b) return a;for (int i = depth_bound - 1; i >= 0; i--)if (anc[a][i] != anc[b][i]) {a = anc[a][i];b = anc[b][i];}return anc[a][0];
}int main() {//freopen("input.txt", "r", stdin);int kase; read(kase);while (kase--) {read(n); init();for (int i = 1; i <= n - 1; i++) {int aa, bb;read(aa); read(bb);G[aa].push_back(bb);G[bb].push_back(aa);pre[bb] = aa;}int root;for (int i = 1; i <= n; i++)if (pre[i] == -1) { root = i; break; }dfs(-1, root, 0);get_anc();int aa, bb;read(aa); read(bb);printf("%d\n", lca(aa, bb));}return 0;
}Codeforces Round #378 (Div. 2)
F. Drivers Dissatisfaction
PS：以上都是为本题作铺垫。。。
题意：
有n(2<=n<=210^5)个城市和m(n-1<=m<=210^5)条双向的道路，每条道路连接一对城市，且每条道路都有一个司机的愤怒值wi(1<=wi<=10^9)，对于每条道路我们还知道降低愤怒值的花费ci(1<=ci<=10^9)，就是降低该条道路一点愤怒值需要ci的花费，也就是说，降低该条道路k点愤怒值，需要k*ci的花费，注意到，愤怒值可以为零甚至负数。现在为了响应国王的号召，需要从m条道路中选择其中n-1条使之成为主干道，这些主干道要使得从任意一个城市都可通过这n-1条主干道抵达任意另外一个城市，国王给的预算为S(0<=S<=10^9)，现要求在花费不超过预算S的前提下，选出n-1条作为主干道，并且降低它们的愤怒值，使得愤怒值之和越小越好。题目保证原图连通。
分析：
MST+LCA倍增。假如我们已经选定了某n-1条道路作为主干道，最优做法就是选这n-1条道路里ci值最小的道路，S全花在这条道路上，但是关于怎么选出这n-1条道路，先按wi为权值构造一颗MST，然后选出MST中ci值最小的道路，算出初始最优解，再对这棵MST进行lca倍增预处理，枚举不在mst里的每条边，如果它如果要被选为主干道，肯定是作为选定ci的道路被选中，假设这条边为(u,v)，找出mst上u和v路径上最大wi的那条边，如若删除这条边，加入(u,v)，若更优则更新最优解。时间复杂度为O((m+n)logn+mlogm)。代码足足打了好几遍，对于大数据一直wrong answer，debug了好久还是无解，我还是太菜了，我已经放弃了这题，所以就没有代码可以贴了。。