This page looks best with JavaScript enabled

「SDOI2013」直径-树的直径

 ·  ✏️ About  1700 words  ·  ☕ 4 mins read · 👀... views

定义一棵树上最长的路径为树的直径。树的直径可能不唯一。

给定的一棵 $n$ 个结点的树,求其直径的长度,以及有多少条边满足所有的直径都经过该边。

链接

Luogu P3304

BZOJ 3124

题解

很有趣的一道题

首先找直径。先从任取点 $t$ 出发,到达最远的一个点 $u$ 。再从 $u$ 出发,到达最远的点$v$,$u$,$v$之间的路径即为树的直径。

这比较显然。

令 $\delta (u,v)$ 为 $u,v$ 两点间路径,其数值即为路径长度。

引理:在一棵树中, $x$ 、 $y$ 和 $z$ 是三个不同的结点。当 $x$ 到 $y$ 的最短路与 $y$ 到 $z$ 的最短路不重合时,$x$ 到 $z$ 的最短路就是这两条最短路的拼接。

定理1:在一棵树中,以任意结点出发所能到达的最远结点,一定是该树直径的端点之一。

证明:假设这条直径是 $\delta (u,v)$ 。分两种情况:

当出发结点 $y$ 在 $\delta(u,v)$ 上时,假设到达的最远结点 $z$ 不是 $u,v$ 中的任一个。这时将 $\delta(y,z)$ 与不与之重合的 $\delta(y,u)$ 拼接(也可以假设不与之重合的是直径的另一个方向),可以得到一条更长的路径,矛盾。

当出发结点 $y$ 不在 $\delta(u,v)$ 上时,分两种情况:

  • 当 $y$ 到达的最远结点 $z$ 横穿 $\delta(u,v)$ 时,记与之相交的结点为 $x$。此时有 $\delta(y,z)=\delta(y,x)+\delta(x,z)$ 。而此时 $\delta(y,z)>\delta(y,v)$ ,故可得 $\delta(x,z)>\delta(x,v)$ 。由 $1$ 的结论可知该假设不成立。

  • 当 $y$ 到达的最远结点 $z$ 与$\delta(u,v)$不相交时,记 $y$ 到 $v$ 的最短路首先与 $\delta(u,v)$ 相交的结点是 $x$。由假设 $\delta(y,z)>\delta(y,x)+\delta(x,v)$ 。而 $\delta(y,z)+\delta(y,x)+\delta(x,u)$ 又可以形成 $\delta(z,u)$ ,而 $\delta(z,u)>\delta(x,u)+\delta(x,v)+2\delta(y,x)=\delta(u,v)+2\delta(y,x)$ 矛盾。


先求出了直径,我们就发现一件好玩的事情。

定理2:对于一个边权为正数的树,其所有的直径必然两两有交点。

证明:设树的一条直径为 $\delta (u,v)$ ,任取另一直径为 $\delta (u’,v’)$ 。其长度设为 $d$ 。

若两直径有公共部分,显然有公共点。

若没有公共部分,则必有一条路径 $\delta (x,y)$ 连接两条直径, $x$ 在 $\delta (u,v)$ 上, $y$ 在 $\delta (u’,v’)$ 上。

在 $\delta(u,x)$ 和 $\delta(x,v)$ 中,不妨设 $\delta(u,x) \geq \frac{1}{2} \times d$ 。同理设 $\delta(u’,y) \geq \frac{1}{2} \times d$ ,又因为 $\delta (x,y) > 0$ ,所以 $\delta (u,u’) = \delta(u,x) + \delta(x,y) + \delta(y,u’) > d = \delta(u,v)$ ,矛盾。


我们要求的是有多少个边在在所有的直径上。我们已经求得了一条直径 $\delta(u,v)$ 。

令 $x$ 为在 $\delta(u,v)$ 上离 $u$ 点最远的点,满足存在点 $u'$ ,使得 $\delta(x,u’) = \delta(x,u)$ ,且 $u \neq u'$ ,则可得 $\delta(u’,v)$ 也是一条直径。

同理 $y$ 为在 $\delta(u,v)$ 上离 $v$ 点最远的点,满足存在点 $v'$ ,使得 $\delta(x,v’) = \delta(x,v)$ ,且 $v \neq v'$ ,则可得 $\delta(u,v’)$ 也是一条直径。

这两个东西都可以在找出直径之后一边扫直径一边 dfs出来。这个时候我们注意到, $x$ 应当在 $y$ 左侧,且 $x$ 在直径左半部, $y$ 在直径右半部,排列顺序大概是这个样子 $u\leftrightarrow x \leftrightarrow y \leftrightarrow v$ 。很容易看出, $x$ 与 $y$ 之间的部分,就是所有直径的公共边。答案即为 $\delta(x,y)$ 。

时间复杂度大约是一个常数比较大的 $O(n)$ 。

代码

懒得写 bfs ,于是就比较的慢…

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <cstdio>
#include <cstring>
#include <vector>
#include <cctype>
#include <algorithm>
#define ll long long
using namespace std;

namespace fast_io {//快速输入模板
    inline char read(){
        static const int IN_LEN=1000000;static char buf[IN_LEN],*s,*t;
        return s==t?(((t=(s=buf)+fread(buf,1,IN_LEN,stdin))==s)?-1:*s++) : *s++;
    }
    inline void read(int &x){
        static bool iosig;static char c;
        for (iosig=false,c=read();!isdigit(c);c=read()){
            if(c=='-')iosig=true;if(c==-1)return;
        }
        for(x=0;isdigit(c);c=read())
            x=((x+(x<<2))<<1)+(c^'0');
        if(iosig)x=-x;
    }
}using namespace fast_io;

const int MAXN = 300000;
struct Edge{
    int from,to,len;
};
int n,u=0,v=0,fa[MAXN];
ll dis[MAXN],ans1,ans2;
vector<Edge> edge[MAXN];
void addedge(int a,int b,int c){
    edge[a].push_back((Edge){a,b,c});
    edge[b].push_back((Edge){b,a,c});
}

void init(){
    read(n);
    int a,b,c;
    for(int i = 1;i<=n-1;i++){
        read(a),read(b),read(c);
        addedge(a,b,c);
    }
}


void dfs(int nown,int f){//寻找从nown节点出发的最长路
    fa[nown] = f;
    for(int i = 0;i<edge[nown].size();i++){
        Edge e = edge[nown][i];
        if(e.to == f) continue;
        dis[e.to] = dis[nown] + e.len;
        dfs(e.to,nown);
    }
}

void find(){
    memset(dis,0,sizeof(dis));
    dfs(1,0);
    for(int i = 1;i<=n;i++)//第一次搜到的节点记作直径的一个端点u
        if(dis[i] > dis[u])
            u = i;
    memset(dis,0,sizeof(dis));
    dfs(u,0);
    for(int i = 1;i<=n;i++)//第二次搜到的节点记作直径的另一个端点v
        if(dis[i] > dis[v])
            v = i;
}

bool dfs2(int nown,ll len){//dfs寻找是否从某个节点存在长度为len的路径
    if(len == 0) return true;
    for(int i = 0;i < edge[nown].size();i++){
        Edge e = edge[nown][i];
        if(e.to == fa[nown]) continue;
        if(dfs2(e.to,len - e.len))
            return true;
    }
    return false;
}

void solve(){
    static int nex[MAXN];
    int t = v,tmp = 0;//tmp为直径长度
    while(t!=u){//记录从u到v的路径
        nex[fa[t]] = t;
        t = fa[t];
        tmp++;
    }
    //l代表到右节点最近的满足上文性质的点,r代表到左节点最近的满足上文性质的点
    int l = 0,r = tmp,nowt = 0;
    //循环中dis[t] = d(u,t)
    for(t = u;t!=v;t = nex[t]){
        for(int i = 0;i<edge[t].size();i++){
            Edge e = edge[t][i];
            if(e.to == fa[t] || e.to == nex[t]) continue;
            if(dfs2(e.to,dis[t] - e.len)) 
                l = max(nowt,l);//寻找离u最远的t,满足d(u',t) = d(u,t),得到即为x,名字叫做l
            else if(dfs2(e.to,(dis[v] - dis[t])- e.len)) 
                r = min(r,nowt);//寻找离v最远的t,满足d(t,v') = d(t,v),得到即为y,名字叫做r
        }
        nowt++;
    }
    ans1 = dis[v];//直径长度
    ans2 = r - l;//在这里事实上是求了r和l的位置并求出ans2
}


int main(){
    init();
    find();
    solve();
    printf("%lld\n%lld\n",ans1,ans2);
    return 0;   
}

cqqqwq
WRITTEN BY
cqqqwq
A student in Computer Science.

评论: