★ 无向无环连通图=树

树上路径问题除了考虑树链剖分，还可以考虑离线树上差分。

树上路径差分：x到根+y到根-lca(x,y)到根+fa[lca(x,y)]到根

【最近公共祖先(LCA)】

void dfs(int x,int fa){    for(int i=1;(1<
      
       <=deep[x];i++)        f[x][i]=f[f[x][i-1]][i-1];    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa)    {        int y=e[i].v;        f[y][0]=x;        deep[y]=deep[x]+1;        dfs(y,x);    }}int find(int x,int y){    if(deep[x]
       
        =0;i--)    if((1<
        
         <=deep[x]&&f[x][i]!=f[y][i])    {        x=f[x][i];y=f[y][i];    }    return f[x][0];}
        
       
      

无向边建两条，数组开大！

倍增数组的构造可以独立出来，只要第一重循环是倍增倍数就可以保证要用的已经算过。

事实证明，简单的路上路径问题用倍增比链剖更有优势。

性质：LCA其实就是两点到达根节点的路径的最近交点。

性质：树上n个点至多有n-1个LCA，就是每两个dfs序相邻点的LCA。

【树链剖分】

为什么要把节点数多的子树作为重链？因为对于同一根，重链查询最快，而轻链必须跳一步才能到重链，这就最大程度减少跳跃次数。

假设最左端叶子节点要查询1次，则必须树大小为1*2+1=3；查询两次，树大小为3*2+1=7；也就是说对于节点数n的树剖分后查询的跳跃次数至多为log(n)次。

不过，如果要把链再放到线段树处理就是O(log²(n))了。

（模板）

void dfs1(int x,int fa){    size[x]=1;    for(int i=first[x];i;i=e[i].from)     if(e[i].v!=fa)      {          int y=e[i].v;          deep[y]=deep[x]+1;          fa[y]=x;          dfs1(y,x);          size[x]+=size[y];      }}void dfs2(int x,int tp,int fa){    int k=0;    pos[x]=++dfsnum;    top[x]=tp;    for(int i=first[x];i;i=e[i].from)     if(e[i].v!=fa&&size[e[i].v]>size[k])k=e[i].v;    if(k==0)return;    dfs2(k,tp,x);    for(int i=first[x];i;i=e[i].from)     if(e[i].v!=fa&&e[i].v!=k)dfs2(e[i].v,e[i].v,x);}int find(int x,int y){    int sum=0;    while(top[x]!=top[y])//while不是if     {         if(deep[top[x]]
      
       pos[y])swap(x,y);    lca=x;    sum+=seg_sum(1,pos[x],pos[y]);    return sum;}
      

过程：

<dfs1>计算子树节点数，同时记录深度和父亲。

<dfs2>分配pos编号并计算top链

<solve>top不同时深度大的往上靠（注意是比较top的深度！注意用while不是if！），同top后pos

求LCA：询问时u,v往同一条重链靠近，到达同一条重链时，pos较小的就是LCA。

【树的直径】

树上简单最长路，树上最远点对。

证明：

求树的直径：①从任意点BFS找到树的直径一端，再从该点BFS找到直径。②DP记录最深和次深，组合比较最长路。

拓展：树的直径相当于选择整棵树为点集的树上最远点对，故选定点集的树上最远点对也有以下性质。

性质：距离树上任意点的最远的点一定是直径的一端（因为直径的证明没有涉及选定点本身，所以任意点可以是点集外的点）。

 

【树上所有点的最远点】<1>第一次tree dp，得出f[i]表示i为根的子树的最深叶子路径，g[i]表示次深叶子路径。<2>第二次treedp，对于节点x，传下来s表示向上的最长路，所以s[x]=max(s,f[x])。遍历x儿子son[x]时s的传递：若f[son[x]]+1=f[x]则s=g[x]+2否则s=f[x]+2。

【树的重心】

引用自：

重心的三个等价定义：

<1>最大的子树节点数最小

<2>子树节点数均<=sum/2（否则往子树移动，根往上这棵树更小）（当存在子树节点数为sum/2时，该子节点也为重心，即双重心）

<3>★所有点到重心的距离和最小

树形DP求重心：令d[i]为节点数，则d[i]=∑[j]+1，对于不同节点i，比较所有节点的max(d[j],n-d[i])的大小。

重心也可以基于点权定义，也就是d[i]=∑d[j]+w[i]，定义sum=∑w[i]，比较所有节点的max(d[j],sum-d[i])。

★例题：

【虚树】

当询问总数有限制时，我们可以对每个询问建虚树，每次复杂度为O(ki)，总复杂度O(Σki)。

虚树中保留特殊点和之间的LCA，根据k个点的相互LCA集合是按dfs排序后所有相邻点的LCA，可以快速求出虚树中的点。

然后按dfs序入栈，若栈顶不是当前点的祖先则弹出栈顶，若是则连边，如此可以快速建出虚树。

注意：垃圾回收保证复杂度。特殊点数组开两倍以存多余的LCA。

例题：