「SDOI2013」直径-树的直径

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

给定的一棵$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;
}