猫史档案馆

树的直径

 

 

一棵树上的最长链或最长链的长度称作这棵树的直径。

图中，蓝色是一条直径，紫色是另一条直径。

 

 

直径求法

 

直径的求法通常有三种。

 

合并链法（树形dp）

 

第一种写法

dfs 找出每个节点下的最长链 m1​ 和次长链 m2​。

每次 dfs 使 ans 的值为最长和次长链的合并结果即可。

int dp(int x,int fa)
{
    int m1=0,m2=0;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(y!=fa)
        {
            int r=dp(y,x)+edge[i];
            if(m1<r)m2=m1,m1=r;
            else if(m2<r)m2=r;
        }
    }
    ans=max(m1+m2);
    return m1;
}

 

第二种写法

树上动态规划求法有另一种写法。

设 dx​ 为从 x 出发走向以 x 为根的子树的最远距离。我们可以通过此求出 fx​ 即经过 x 的最长链长度。

 

求解 fx​ 事实上就是合并最长链和次长链的过程。我们可以自底向上地统计结果。

当回溯到一个节点 x 的时候，设其任意一个子节点为 y，我们直接将 dx​ 更新为 max(dx​,dy​+w(y,x))。

这个转移的意义是，在搜索子节点的时候，将 目前求出的最长链 与其 子节点 y 的最长链加上 w(y,x) 边 这条候选的最长链作比较。

 

全局变量 ans=max(ans,dx​+dy​+w(y,x))，即是计算两条链的长度之和。

void dp(int x)
{
    v[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(!v[y])
        {
            dp(y);
            ans=max(ans,d[x]+d[y]+edge[i]),
            d[x]=max(d[x],d[y]+edge[i]);
        }
    }
}

 

 

两次搜索

 

使用两次搜索的方法能够求出直径的端点和直径的路径。

任取一个点 x，以 x 为根寻找距离 x 最远的点 p；然后以 p 为根同样寻找到离 p 最远的点 q，p 和 q 就是直径的两个端点。

记 dx​ 为到根的距离，简单搜索即可。

 

正确性证明

p 必然是直径的一端。

如果不是，设另一点 y 是直径的一端，因为求出的 p 是距离 x 最远的点，所以 dis(p,x)>dis(y,x)。

这与直径最长性矛盾，所以找不到符合要求的点 y，所以 p 是直径的一端。

 

同理，q 是距离直径的一端 p 最远的点，自然就是直径的另一端。

 

BFS求解（广度优先搜索）

int bfs(int s)
{
    int x,y;
    memset(d,0x3f,sizeof(d));
    q.push(s),d[s]=0,pre[s]=0;
    while(q.size())
    {
        x=q.front(),q.pop();
        for(int i=head[x];i;i=next[i])
            if(d[ver[i]]>=INF)
                d[ver[i]]=d[x]+edge[i],
                pre[ver[i]]=x,          //记录前驱(路径) 
                q.push(ver[i]);
    }
    for(x=1,y=1;x<=n;x++)
        if(d[x]>d[y])y=x;
    return y;
}

//主函数中 
    p=bfs(1);
    q=bfs(p);

 

DFS求解（深度优先搜索）

int dfs1(int x,int fa)
{
    int pnt;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(y!=fa)
        {
            d[y]=d[x]+edge[i],pre[y]=x;
            if(d[y]>d[pnt])pnt=y; 
            dfs1(y,x);
        }
    }
    return pnt;
}

//主函数中 
    p=dfs1(1,-1);
    memset(d,0x3f,sizeof(d));
    q=dfs2(p,-1); 

 

 

直径的简单应用

 

LuoguP4408 NOI2003 FromCCF

（中国信息学奥林匹克竞赛 2003年）

 

在一棵无根树上，找 A,B,C 三个点，使得 AB+BC(AC>BC) 或 AC+AB(BC>AC) 最大。

 

Solution

找直径没有问题罢。

找完之后我们枚举直径外其他的点，这些点和俩端点形成类似于一个三角形的东西。

然后直径这条边是必须选的，剩下两条边要考虑走哪条边。

题目告诉你先走近的，所以剩下俩边选取短的那条就行了。

然后这些点都枚举完之后取最大值即可。

 

 

 

树的中心

 

 

一棵树的中心 x 满足，在树上所有的点中，到 x 的最大距离最小。

 

 

中心的性质及证明

 

树的中心有一个很好的性质：

一棵树的中心是直径的中点 。

这里的中点是考虑边权的。

 

性质证明

 

根据两次搜索的证明，我们已经知道距离任意一个点最远的点 p 是直径的端点，而 p 到达 x 必然先经过直径的一段。

假设路径 (p,x) 拐出直径的点为 y，则我们先要最小化 dis(p,y)+dis(x,y)。

因为 dis(p,y) 在 y 固定时是不变的，因此我们当然让 dis(x,y)=0，即 x 在直径上。

那么我们的 y 点（即 x）如何选取？也就是使 max(dis(p,y),dis(q,y)) 最小，显然 p 在直径的中点上。

证毕。

 

 

中心的求解方法

 

那么中心怎么求呢？

其实只需要这么一句话：

for(int i=1;i<=(d[q]+1)/2;i++)x=pre[x];

 

如果是带边权的话，我们可以记录 pre 的同时记录边权，然后先求出直径长度，接着直径上每个点扫描过去，判断一下长度即可。

 

 

 

本期总结

 

 

这期教程，我们学习了树的直径、中心求解和性质。

学会这期教程之后，你的树形结构内容就已经入门了，或许也有了解决 CSP-J 中树上问题的能力。

并且本期教程已经超出了 CSP-J 的内容，涉及了提高组的知识点。

当然，树的内容远不止这些。下期我们学习直径和中心的重要应用，将解决更加复杂的问题。

本期教程是以下教程计划的内容：

https://shequ.codemao.cn/community/380955

 

大家也可以前往我的 Luogu 博客学习：246979.blog.luogu.org