长链剖分小结

· · 个人记录

前言

有的时候，我们会遇到一些与深度相关的树形 dp。

比如说 CF1009F，这一道题目可以说是一个很标准的典范。

这个题目的大意其实很简单：有一个有 n 个节点的树 T，设 d(u,x) 为 u 子树中到 u 距离为 x 的节点数。对于每个点 u，求一个最小的 k，使得

d(u,k)$ 最大。$n \leq 10^6

首先如果这个 n 没有到 10^6 量级，假设 n=10^3，那么这个题目就是一个普及组难度的树形 dp。这个 d 的定义，其实就可以作为我们状态的定义。也就是定义 dp[u][i] 为以 u 为根的子树中，与 u 距离为 i 的点的个数。

那么显然就可以推出下面的方程式：

\begin {cases}dp[u][0]=1\\ dp[u][i]=\sum_{v \in son} dp[v][i-1] \end{cases}

这样的一个 dp 是 O(n^2) 的，显然对于 n=10^3 的数据过得了，但是肯定过不了 n=10^6 的数据。这个时候肯定就要想想别的方法了，比如说先怀疑这个题是不是真的是个 dp，或者说，这个 dp 是不是可能有优化的空间。

又比如说，你看到了一道题目，给定一个有 n 个点的有根树 T，有 q 次询问，每次询问节点 u 的 k 级祖先。强制在线。

这个题目你觉得好像轻重链剖分能做，开开心心写了个轻重链剖分，时间复杂度是 O(n+q \log n)，然后就开开心心 TLE 了。然后你就去看题解了。

那么既然到了这里，那么就要引出本篇的主角：长链剖分了。

长链剖分的简介

长链剖分属于树链剖分的一种。我们平时经常会写一种树链剖分，以 O(\log n) 单次查询两个点的最近公共祖先的那种树链剖分，叫做（轻）重链剖分。也就是对于每个节点 u，找到它最大的一个子树（即：这个子树中包含最多个节点），让那个子树的根 v 作为重儿子，u 的其他儿子叫做轻儿子。而长链剖分是类似的，不过它找的不是最大的一个子树，是最深的一个子树。也就是说，把子树深度最大的那个儿子作为重儿子。

这样一来，是不是和轻重链剖分是不是很像呢？的确，从代码上来说，是很像。我们只要把原来记录 size 的数组变成 dep[u] 以记录 u 在整棵树中的深度，再开一个数组叫做 maxdep[u] 以记录 u 的各个儿子的最大深度，这样就可以仿照之前的轻重链剖分去维护现在这个新定义下的重儿子。代码如下：

inline void dfs1(int u,int fa)
{
    dep[u]=dep[fa]+1;
    maxdep[u]=dep[u];
    ::fa[u]=fa;
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v!=fa)
        {
            dfs1(v,u);
            maxdep[u]=max(maxdep[u],maxdep[v]);
            if (maxdep[v]>maxdep[son[u]])
                son[u]=v;
        }
    }
}

inline void dfs2(int u,int fir)
{
    ide[u]=++dfs_clock;
    rid[dfs_clock]=u;
    top[u]=fir;
    len[u]=maxdep[u]-dep[top[u]]+1;
    if (son[u])
        dfs2(son[u],fir);
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v!=fa[u] && v!=son[u])
            dfs2(v,v);
    }
}

长链剖分的性质

不过光有代码是没用的，因为代码这东西背熟了之后也就 2 分钟可以写完。我们应该把我们的眼光，聚焦在长链剖分可能会有的一些优秀性质中。我们可以回顾一下我们之前所熟悉的重链剖分，看看有哪些相似之处。

首先，我们会发现：每个点都必定在也且仅在一条长链上，这样就保证长链的长度之和为 O(n) 级别。

接着，回想我们之前学习重链剖分的时候有一个很重要的性质：从一个点往上跳到树的根，那么必然会经过不超过 \log |T| 次（|T| 为树的节点个数）重链。这也就使得重链剖分对于很多操作——例如求两个点之间的最近公共祖先的时间复杂度是 O(\log |T|) 这么一个非常优秀的复杂度。

那么长链剖分是否会有类似的性质呢？这个可能相对来说不是那么显然。我们注意到，如果从一个点开始往上跳，从一条长链 S_1 跳到另一条长链 S_2，那么跳到的这条长链 S_2 的长度，必定会不小于之前所跳到的那个长链的长度 S_1，这是由长链的性质决定的，如果 |S_2|<|S_1|，那么这个 S_2 必定就不是长链了。

那么就可以显然找到一个最坏情况：跳上去的长度分别为 1,2,3,\cdots,\sqrt{n}，也就是一点一点地往上跳到根，这样就可以得出一个重要结论：对于树上的任何一个点跳到根，需要经过不超过 O(\sqrt{n}) 条长链。如果单从这一点来看，好像长链剖分似乎并没有什么用。

之前的重链剖分是可以 O(\log |T|) 的时间复杂度求出最近公共祖先的，那么长链剖分的这种剖分方式，是否有助于求出公共祖先，其实是可以的。长链剖分的性质可以保证一点：对于任何一个节点 u，其 k 级祖先 v 所在链的长链的链长一定会 \geq k。这是可以通过分类讨论进行证明的：

那么这也就让人感觉到：虽然长链剖分可能不一定能很好地求出最近公共祖先，也对公共祖先也可能没有什么帮助，但是对于求k次祖先，却有着很好的助益。

长链剖分的应用

k 级祖先

我们考虑下面这个题：

给定一个有n个点的有根树T，有q次询问，每次询问节点u的k级祖先。强制在线。

首先我们有一个很显然的做法，采用之前的轻重链剖分。如果往上跳k次，跳出重链链头的时候就到它的父亲节点再继续跳，否则如果卡在重链中间，那么就直接扫过去即可。时间复杂度O(n+q \log n)

而在哪条重链上是可以二分的，重链又只会被经过\log n次，那么时间复杂度就变成了O(n+q \log \log n)

但是这些做法都有一个缺点——查询的时候不能做到O(1)完成。但是长链剖分是可以的！

我们回到长链剖分的性质上。其中有一条就是：对于任何一个节点u，其k级祖先v所在链的长链的链长一定会\geq k。那么如果将其折半变成k'，那么也会有一样的性质。这可以启发我们一件事情：我们只要找到一个k'级祖先，就可以根据一条长链从上到下的每一个点，以及长链的顶端，以及长链长度个祖先，是不是就可以求出k次祖先了呢？答案当然是可以的，而且因为很多东西都是可以被预处理到的，因此单次计算的时间复杂度就变成了O(1)，所以我们的问题就在于如何去求出k'级的祖先。

这个思路就自然许多了。很明显如果直接去用倍增或者其他的做法求出k’级祖先，我们做的努力就全部白费。不过上述的做法只要满足k'>\frac{k}{2}即可实现了，因此可以预处理k的最高二进制位，就可以快速地处理出k’级祖先，也进而可以快速地处理出k级祖先了。

接下来计算时间和空间复杂度：因为所有长链的链长之和为O(n)级别，故维护长链顶点、长链长度个祖先和整条链，都是O(n)的。而最高二进制位可以使用一些位运算的小技巧去实现，这也是O(n)的。时空复杂度瓶颈在倍增上，为O(n \log n)。故预处理复杂度为O(n \log n)，总体时间复杂度为O(n \log n + q)。

那么具体预处理步骤如下：

对于查询，步骤如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <vector>

using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,fa[500050][20],dep[500050],maxdep[500050],ide[500050],rid[500050],top[500050],len[500050],son[500050],dfs_clock;

vector <int> G[500050],U[500050],D[500050];

int heavy_bit[500050];

inline void dfs1(int u,int fa)
{
    dep[u]=dep[fa]+1;
    maxdep[u]=dep[u];
    ::fa[u][0]=fa;
    for (int i=1;i<20;i++)
        ::fa[u][i]=::fa[::fa[u][i-1]][i-1];
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v!=fa)
        {
            dfs1(v,u);
            maxdep[u]=max(maxdep[u],maxdep[v]);
            if (maxdep[v]>maxdep[son[u]])
                son[u]=v;
        }
    }
}

inline void dfs2(int u,int fir)
{
    ide[u]=++dfs_clock;
    rid[dfs_clock]=u;
    top[u]=fir;
    len[u]=maxdep[u]-dep[fir]+1;
    if (son[u])
        dfs2(son[u],fir);
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v!=fa[u][0] && v!=son[u])
            dfs2(v,v);
    }
}

inline int Query(int u,int k)
{
    if (k>dep[u])
        return 0; //不存在k级祖先
    if (!k)
        return u; //第0级祖先就是自己
    u=fa[u][heavy_bit[k]];
    k^=1<<heavy_bit[k]; //倍增先找祖先，然后看是走向下的还是走向上的链。 
    if (!k)
        return u;
    int delta=dep[u]-dep[top[u]];
    if (delta==k)
        return top[u];
    else if (delta>k)
        return D[top[u]][delta-k-1];
    else
        return U[top[u]][k-delta-1]; 
}

unsigned int s;

inline unsigned int get(unsigned int x)
{
    x^=x<<13;
    x^=x>>17;
    x^=x<<5;
    return s=x;
}

int main()
{
    n=read();
    int q=read(),root;
    cin >> s;
    for (int i=1;i<=n;i++)
    {
        int f=read();
        G[f].push_back(i);
        G[i].push_back(f);
        if (f==0)
            root=i;
    }
    int ans=0;
    dfs1(root,0);
    dfs2(root,root);
    /*
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<20;j++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
    }
    */
    for (int i=1;i<=n;i++)
    {
        if (i==top[i])
        {
            for (int j=1,x=i;j<=len[i] && x!=root;j++)
            {
                x=fa[x][0];
                U[i].push_back(x);
            }
            for (int j=1,x=i;j<=len[i];j++)
            {
                x=son[x];
                D[i].push_back(x);
            }
        }
    }
    int maxv=1;
    for (int i=1;i<=n;i++)
    {
        if ((i>>maxv)&1)
            maxv++;
        heavy_bit[i]=maxv-1;
    }
    long long fans=0;
    for (int i=1;i<=q;i++)
    {
        int a=(get(s)^ans)%n+1;
        int b=(get(s)^ans)%dep[a];
        //printf("%d\n",(ans=Query(a,b)));
        ans=Query(a,b);
        fans^=(1LL*ans*i);
    }
    cout << fans << endl;
    return 0;
}

优化以深度为下标的信息合并

CF1009F

我们回到我们前言的第一个题。不过为了节省你的时间，我再在这里放一遍题意和我们所得出来的式子：

有一个有n个节点的树T，设 d(u,x) 为 u 子树中到 u 距离为 x 的节点数。对于每个点u，求一个最小的 k，使得 d(u,k) 最大。n \leq 10^6

考虑n=10^3，那么这个题目就是一个普及组难度的树形dp。这个d的定义，其实就可以作为我们状态的定义。也就是定义dp[u][i]为以u为根的子树中，与u距离为i的点的个数。

那么显然就可以推出下面的方程式：

\begin {cases}dp[u][0]=1\\ dp[u][i]=\sum_{v \in son} dp[v][i-1] \end{cases}

现在我们学完了长链剖分，对它有没有想法？

用len[u]表示u到叶子节点的最长距离。（注意之前的长链剖分的len[u]表示重链长度）那么dp[u][i]的第二维显然不会超过len[u]，那么我们可以考虑对于每一个长链的链头，开一个大小为len[u]的内存池。

这样我们对于每一条长链t，里面的第i个元素t_i，就可以用内存池的第i个位置存储f[t_i][0]

那么对于长链，我们就做好了——我们可以直接让父节点从子节点更新答案。

如果不是长链，那么我们只需暴力在重链顶部合并即可。因为链长度总共为O(n)，而每条链最多只会被合并1次，时间复杂度就到了很优秀的O(n)。

注意一定得开内存池，不能直接开第二维进行存储，不然空间会炸。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cctype>
#include <vector>
#include <queue>

using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int fa[1000050],son[1000050],len[1000050],maxlen[1000050];

vector <int> G[1000050];

inline void dfs(int u,int f,int dep)
{
    fa[u]=f;
    maxlen[u]=len[u]=dep;
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v!=f)
        {
            dfs(v,u,dep+1);
            maxlen[u]=max(maxlen[u],maxlen[v]);
            if (maxlen[v]>maxlen[son[u]])
                son[u]=v;
        }
    }
}

int ans[1000050],*dp[1000050],tmp[1000050<<5],*now=tmp+1;

inline void assign(int u)
{
    dp[u]=now;
    now+=maxlen[u]-len[u]+1;
}

inline void DP(int u)
{
    if (son[u])
    {
        dp[son[u]]=dp[u]+1;
        DP(son[u]);
        ans[u]=ans[son[u]]+1;
    }
    dp[u][0]=1;
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v!=fa[u] && v!=son[u])
        {
            assign(v);
            DP(v);
            for (int j=0;j<=maxlen[v]-len[v];j++)
            {
                dp[u][j+1]+=dp[v][j];
                if (dp[u][j+1]>dp[u][ans[u]] || (dp[u][j+1]==dp[u][ans[u]] && ans[u]>j+1))
                    ans[u]=j+1;
            }
        }
    }
    if (dp[u][ans[u]]==1)
        ans[u]=0;
}

int main()
{
    int n=read();
    for (int i=1;i<n;i++)
    {
        int u=read(),v=read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0,1);
    assign(1);
    DP(1);
    for (int i=1;i<=n;i++)
        cout << ans[i] << endl;
    return 0;
}

那么上面这个题应该属于练手难度。接下来有两个有一定难度的题目。

[POI2014] HOT-Hotels

题目链接

题目大意：给出一棵有 n 个点的树，求有多少组点 (i,j,k) 满足 i,j,k 两两之间的距离都相等。

首先原题是$n \leq 10^3$的。我们先根据原题的数据规模，思考一个做法出来。 题目要求三个点两两距离相同，而且树是没有边权的，这也就意味着三个点有一个公共的LCA。但是三个点有公共LCA的个数不太好求，但是我们可以考虑在这个点去计数。 首先考虑$f[u][i]$为在$u$的子树中，距离$u$为$i$的点数。这个和上面一题类似不再赘述。 然后再考虑$g[u][i]$在$u$的子树中，有两个点到LCA的距离为$d$，而且他们的LCA到$i$的距离为$d-j$的点对数。这个转移比较难想。 $g[u][i]+=\begin{cases}\sum_{v \in son} g[v][i-1]\\ \prod_{v \in son} f[u][i]\times f[v][i-1]\end{cases}

而ans可以根据f和g进行拼接：

ans+=\begin{cases}\sum_{v \in son} g[u][i] \times f[v][i-1] \text{u处理好的选两个，与v拼}\\ \sum_{v \in son}f[u][i] \times g[v][i+1]\text{v处理好的选两个，与u拼}\end{cases}

这样就是O(n^2)的算法了。

那么我们考虑使用长链剖分进行优化。类似上面我们开一个内存池，那么f[u]=f[son]-1,g[u]=g[son]+1然后每次转移分成两步走：一次从重儿子直接转移，即O(1)，一次从轻儿子，在重链的顶部转移，这样转移的时间复杂度是重链长度，即O(\sum len)。因为一个点只有一个父亲，所以一条重链仅仅只会被暴力转移一次。故总时间复杂度为O(n)。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>

using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n;

vector <int> G[100050];

int fa[100050],dep[100050],son[100050],maxdep[100050];

inline void dfs(int u,int fa)
{
    ::fa[u]=fa;
    dep[u]=dep[fa]+1;
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v!=fa)
        {
            dfs(v,u);
            maxdep[u]=max(maxdep[u],maxdep[v]);
            if (maxdep[v]>maxdep[son[u]])
                son[u]=v;
        }
    }
    maxdep[u]=maxdep[son[u]]+1;
}

long long *f[100050],*g[100050],pool[500050],*pos=pool,ans;

inline void assign(int u)
{
    int add=maxdep[u]<<1;
    f[u]=pos;
    pos+=add;
    g[u]=pos;
    pos+=add;
}

inline void solve(int u,int fa)
{
    if (son[u])
    {
        f[son[u]]=f[u]+1;
        g[son[u]]=g[u]-1;
        solve(son[u],u);
    }
    f[u][0]=1;
    ans+=g[u][0];
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v!=fa && v!=son[u])
        {
            assign(v);
            solve(v,u);
            for (int j=0;j<maxdep[v];j++)
            {
                if (j>0)
                    ans+=f[u][j-1]*g[v][j];
                ans+=f[v][j]*g[u][j+1];
            }
            for (int j=0;j<maxdep[v];j++)
            {
                g[u][j+1]+=f[u][j+1]*f[v][j];
                if (j>0)
                    g[u][j-1]+=g[v][j];
                f[u][j+1]+=f[v][j]; 
            }
        }
    }
}

int main()
{
    n=read();
    for (int i=1;i<n;i++)
    {
        int u=read(),v=read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    //for (int i=1;i<=n;i++)
    //  cout << maxdep[i] << endl;
    assign(1);
    solve(1,0);
    cout << ans << endl;
    return 0;
}

[WC2010] 重建计划

题目链接

这道题目可以用点分治之类的做法做。但是我点分治不熟。

不过这个题有一个长链剖分的方法。

显然可以发现，答案是可以被二分的。假设我们已经二分的值是mid

对AvgValue的计算式子进行一些推导变形。

\frac{\sum_{e \in S} v(e)}{|S|} \geq mid \sum_{e \in S}v(e) \geq |S| \times mid \sum_{e \in S} v(e)-|S| \times mid \geq 0

因为\sum_{e \in S} v(e)一共有|S|项，故可以考虑合并，则有

\sum_{e \in S}(v(e)-mid) \geq 0

那么我们可以在二分的时候，每二分到一个值mid，便把边权临时减去一个值mid。那么一个合法的路径，就只需要使得路径上每一条边，其被减过的边权之和\geq 0。然后我们需要找到一个最大的边权和。

问题就在于：怎么找到这么一条路径。首先我们会发现这是个树形dp。我们假设f[u][i]表示以u为根，往外走i个点，边权和的最大值。这样，我们把一个树可以拆成两半，一半是u为根的处理f[u][i]的子树，另一半的子树中，我们只要找到一个最大值，使得两边拼起来最大即可，也就是有[lb-j,ub-j]（lb,ub分别对应题目中的l,u，只是我这里u冲突了）条边中的最大值即可。

这样做，时间复杂度是O(n^2 \log v)的，也就是说，大概可以拿个20分。

那么做到这里了，我们可以考虑优化。注意到这个i的意思，其实是深度的意思。优化一个以深度作为下标的dp，我们自然可以想到长链剖分，这是因为我们可以把和深度有关的信息，全部存到长链上。

因此我们进行树形dp的时候，我们可以考虑对于重儿子的回溯不做任何操作，而对于轻儿子，我们可以去枚举轻儿子的每一个可能的深度的权值和的最大值，接着就在长链上的区间去查询最大值去更新答案，再将现在轻儿子已经有的信息更新到长链上即可。这样子做，会把每个子树的有用的信息，挂在这个子树的根所在的那个长链上。不过如果直接开内存池，可能空间难以承受。因为信息可以被快速合并，我们只需要一个单点修改，区间求最大值的线段树，辅助完成信息的合并即可。

这样我们每次进行dp，所需的时间复杂度是O(n \log n)，加上一开始进行的分数规划，那么总得时间复杂度就是O(n \log n \log v)，可以跑出来了。

注意一下变量类型问题，这个题注意边权相关的东西，都要开double类型，防止中间计算的时候丢失小数点后面的位，而产生精度误差。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <vector>

using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

#define next Syameimaru_Aya

int n,L,U,a[100050],b[100050],u[100050];

vector <int> G[100050],W[100050];

vector <double> w[100050];

int dep[100050],maxdep[100050],fa[100050],son[100050],ide[100050],rid[100050],dfs_clock=0,top[100050],id[100050];

double dis[100050];

int head[200050],tail[200050],next[200050],ecnt=0;

double W1[200050],w1[200050];

inline void link(int u,int v,double dis)
{
    tail[++ecnt]=v;
    W1[ecnt]=dis;
    next[ecnt]=head[u];
    head[u]=ecnt;
    tail[++ecnt]=u;
    W1[ecnt]=dis;
    next[ecnt]=head[v];
    head[v]=ecnt;
}

inline void dfs1(int u,int fa)
{
    dep[u]=dep[fa]+1;
    maxdep[u]=dep[u];
    ::fa[u]=fa;
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v!=fa)
        {
            dfs1(v,u);
            maxdep[u]=max(maxdep[u],maxdep[v]);
            if (maxdep[v]>maxdep[son[u]])
                son[u]=v;
        }
    }
}

inline void dfs2(int u,int fir)
{
    ide[u]=++dfs_clock;
    rid[dfs_clock]=u;
    top[u]=fir;
    if (son[u])
        dfs2(son[u],fir);
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v!=fa[u] && v!=son[u])
            dfs2(v,v);
    }
}

const double inf=1145141919810;

struct Seg_Tree
{
    int l,r;
    double val;
}t[500050];

inline void Build(int id,int l,int r)
{
    t[id].l=l;
    t[id].r=r;
    t[id].val=-inf;
    if (l==r)
    {
        ::id[l]=id;
        return;
    }
    int mid=(l+r)>>1;
    Build(id<<1,l,mid);
    Build(id<<1|1,mid+1,r);
}

inline void Change(int id,int pos,double val)
{
    t[id].val=max(t[id].val,val);
    if (t[id].l==t[id].r)
        return;
    int mid=(t[id].l+t[id].r)>>1;
    if (pos<=mid)
        Change(id<<1,pos,val);
    else
        Change(id<<1|1,pos,val);
}

inline double Query(int id,int l,int r)
{
    if (l>r)
        return -inf;
    if (t[id].l>=l && t[id].r<=r)
        return t[id].val;
    int mid=(t[id].l+t[id].r)>>1;
    if (r<=mid)
        return Query(id<<1,l,r);
    else if (l>mid)
        return Query(id<<1|1,l,r);
    else
        return max(Query(id<<1,l,mid),Query(id<<1|1,mid+1,r));
}

double res[100050],ans=0;

inline void dfs(int u)
{
    Change(1,ide[u],dis[u]);
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v==son[u])
        {
            dis[son[u]]=dis[u]+w[u][i];
            dfs(son[u]);
            break;
        }
    }
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (v!=son[u] && v!=fa[u])
        {
            dis[v]=dis[u]+w[u][i];
            dfs(v);
            for (int j=1;j<=maxdep[v]-dep[u];j++)
            {
                res[j]=t[id[ide[v]+j-1]].val;
                if (j<=U)
                    ans=max(ans,Query(1,max(ide[u],ide[u]+L-j),min(ide[u]+maxdep[u]-dep[u],ide[u]+U-j))+res[j]-2*dis[u]);
            }
            for (int j=1;j<=maxdep[v]-dep[u];j++)
                Change(1,ide[u]+j,res[j]);
        }
    }
    ans=max(ans,Query(1,ide[u]+L,min(ide[u]+maxdep[u]-dep[u],ide[u]+U))-dis[u]);
}

int main()
{
    n=read();
    L=read(),U=read();
    for (int i=1;i<n;i++)
    {
        a[i]=read();
        b[i]=read();
        u[i]=read();
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
        W[a[i]].push_back(u[i]);
        W[b[i]].push_back(u[i]);
        link(a[i],b[i],u[i]);
    }
    dfs1(1,0);
    dfs2(1,1);
    double left=0,right=1e6;
    while (right-left>1e-6)
    {
        double mid=(left+right)/2.0;
        for (int i=1;i<=n;i++)
        {
            w[i].clear();
            for (int j=0;j<W[i].size();j++)
                w[i].push_back(W[i][j]-mid);
        }
        for (int i=1;i<=ecnt;i++)
            w1[i]=W1[i]-mid;
        Build(1,1,n);
        ans=-inf;
        dis[1]=0;
        dfs(1);
        //printf("%.5lf %.5lf %.5lf %.5lf\n",left,right,mid,ans);
        if (ans<0)
            right=mid;
        else
            left=mid;
    }
    printf("%.3lf\n",left);
    return 0;
}
//代码写复杂了

小结

长链剖分是一个虽然名气不响亮，但是用处很大的算法。它的三条性质，决定了一旦所需要维护的信息与深度相关联的时候，长链剖分能以一个非常优秀的复杂度对它们进行快速的维护，特别是这些信息可以被快速合并的时候。有时候长链剖分对内存要求较高，还有可能会辅以其他数据结构去优化空间，这也是一种变形了吧。总而言之，这是一种在省选级别或者以上的赛事中，可能会很有用的一种算法。

参考资料

https://www.cnblogs.com/cjyyb/p/9479258.html

https://zhuanlan.zhihu.com/p/25984772