【题解】树的直径泛做

做了做和这一块儿有关的题。

说是泛做然而只做了三道题

1 基础知识

嗯,首先就是考虑一点定义。

  • 树的直径:一棵树内最长的一条简单路径。

然后关于直径有一些性质,大部分都可以拿反证法证出来:

  • 对树上随便一个点 $x$ 而言,与之相距最远的点一定是直径的某个端点。

    • 证明的话可以分类讨论:
        1. 对于直径上一点 $x$,离他最远点设为 $y$,不在直径上,那么直径完全可以从这个地方拐到 $y$ 从而变得更大,与直径的最优性矛盾。
        1. 对于非直径上一点 $x$,离他最远的点为 $y$,不在直径上。那么考虑设 $x$ 到直径上最近一点 $u$ 的距离为 $d_u$,直径远端的距离为 $d$,到 $y$ 的距离为 $d_y$。那么有 $d_y+d_u>d$ 。于是考虑如果让直径从 $u$ 拐到 $y$ 的话显然会更优,与直径的最优性矛盾。
  • 定义一棵树的 中心 为 $\max_{v\in T}{d_{u,v}}$ 最小的点 $u$,那么 $u$ 在直径上。

    • 证明的话考虑如果不在直径上,那么考虑到直径上最近的一点 $p$,发现 $p$ 对于直径的两个端点距离要小于 $p$ 。再结合上面证明过的,对于 $u$ 而言,$\max_{v\in T}{d_{u,v}}$ 一定会在直径上面取到,而 $u$ 的次远点到 $p$ 的距离一定小于 $p$ 到直径端点的距离,所以中心 $u$ 一定在直径上。

这两个结论有事还是很有用的2333


以上是证明着玩的。接下来考虑直径的求法。

首先就是喜闻乐见的两遍 $dfs/bfs$ 求。大概就是考虑第一遍随便选一个点找一个与他相距最远的点 $u$, 那么 $u$ 一定会在直径上。之后再dfs求一遍最远点即可。由于固定了端点所以就直接脑残求就完了。

然而我是这么 $dfs$ 的。回想起来自己是个憨憨:

1
2
3
4
5
6
7
8
9
10
void dfs(int n, int fa){
// cout << n << endl ;
d[n] = 0, pre[n] = 0 ;
for (int k = head[n] ; ~k ; k = next(k)){
if (to(k) == fa) continue ;
dfs(to(k), n) ;
if (d[to(k)] + val(k) > d[n])
d[n] = d[to(k)] + val(k), pre[n] = to(k) ;
}
}

还有一种方法是直接 $dp$ ,这个比较傻,维护最长链和次长链即可。

1
2
3
4
5
6
7
void dp(int n, int fa){
for (int k = head[n] ; ~k ; k = next(k)){
if (to(k) == fa) continue ;
dfs(to(k), n), ans = max(ans, dp[n] + dp[to(k)] + val(k)) ;
dp[n] = max(dp[n], dp[to(k)] + val(k)) ;
}
}

2 例题

1 [APIO2010]巡逻

给定一棵树。可以连 $K~(K\in\\{1,2\\})$ 条额外的边使得从 $1$ 号点出发,遍历所有路径一次,使走的走路程最短。

同时有以下约束:

  • 每条路必须经过至少一次,点可以经过多次。
  • 最后要回到一号点。

发现 $K=1$ 时比较容易考虑,把直径两端连起来放到最后走,这样一定是最优的。于是此时答案为 $2(n-1) - (L-1)=2n-L+1$ 。

然后考虑 $K=2$ 。发现 $K=2$ 时和 $K=1$ 情况大致相似,第一条边连直径。然后考虑第二条边,发现第二条边可能存在连出的圈与第一个圈有相交一部分的情况。但解决方法也很简单,把直径上的边权设置为其相反数即可。

然后就是求两遍直径就完事了233

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
void dfs(int n, int fa){
// cout << n << endl ;
d[n] = 0, pre[n] = 0 ;
for (int k = head[n] ; ~k ; k = next(k)){
if (to(k) == fa) continue ;
dfs(to(k), n) ;
if (d[to(k)] + val(k) > d[n])
d[n] = d[to(k)] + val(k), pre[n] = to(k) ;
}
}
void do_do(int n, int fa){
// cout << n << endl ;
for (int k = head[n] ; ~k ; k = next(k)){
if (!vis[to(k)] || to(k) == fa) continue ;
val(k) = -1, val(k ^ 1) = -1, do_do(to(k), n) ;
}
}
void do_dp(int u, int fa){
for (int k = head[u] ; ~k ; k = next(k)){
if (to(k) != fa){
do_dp(to(k), u),
L2 = max(L2, d[to(k)] + val(k) + d[u]) ;
d[u] = max(d[u], d[to(k)] + val(k)) ;
}
}
}
int main(){
int i, u, v, n ;
cin >> N >> K, cnt = -1 ;
memset(head, -1, sizeof(head)) ;
for (i = 1 ; i < N ; ++ i)
scanf("%d%d", &u, &v), add(u, v) ;
dfs(1, 0) ; n = 1 ;
while (pre[n]) n = pre[n] ;
dfs(n, 0), L1 = d[n] + (bool)(K == 1);
while (pre[n])
vis[n] = 1, n = pre[n] ;
vis[n] = 1 ; //cout << L1 << endl ;
if (K > 1){
do_do(n, 0) ;
memset(d, 0, sizeof(d)) ;
do_dp(3, 0) ;
}
//cout << L1 << " " << L2 << endl ;
cout << 2 * N - L1 - L2 << endl ; return 0 ;
}

2 [NOIp2007]树网的核

给定一棵树 $\rm T=(E,V)$,求一段长度不超过 $s$ 的路径 $p=(\rm e, v)$,最小化:

其中 $\mathrm{path}(u,v)$ 表示 $u,v$ 之间唯一路径上,除去 $u,v$ 的点集。$[~]$ 为艾佛森括号。

$1\leq n\leq 5,000$

类比一开始对中心的位置的证明,可以发现这段路径一定在直径上(事实上可以把这段路径缩成一个点来考虑)。然后就考虑先把直径找出来,然后 $n^2$ 枚举路径端点 $(p,q)$ ,$O(n)$ 算一下最长距离,这样是 $O(n^3)$ 的。然而发现可以贪心,链长期望越长,式子的值期望越小。所以可以 $n^2$ 预处理出来直径上离每个点最远且距离 $\leq s$ 的端点,然后 $n^2$ 做即可。最终复杂度 $n^2$。

3 [SDOI2011]消防

给定一棵树 $\rm T=(E,V)$,求一段长度不超过 $s$ 的路径 $p=(\rm e, v)$,最小化:

其中 $\mathrm{path}(u,v)$ 表示 $u,v$ 之间唯一路径上,除去 $u,v$ 的点集。$[~]$ 为艾佛森括号。

$1\leq n\leq 500,000$

……所以其实就是上一道题的加强版。

考虑怎么优化一下 $n^2$ 的算法,发现两部分都需要优化。首先考虑 n^2 预处理出来直径上离每个点最远且距离 ≤ s 端点 这东西,发现完全可以二分,于是变成了 $\log$ ;然后发现后一部分,完全可以一遍 $dp$ 求出来 “离直径上每个点最远的点的距离”这个东西,然后就可以 $\rm rmq$ 解决。然后两部分就都变成了 $n\log n$ 。(当然你也可以认为 $rmq$ 是 $O(\rm C)$ 的)

但实际上可以继续优化。首先发现的是那个二分可以拿尺取法做掉。之后考虑拿出之前整过的结论操作一下。令 $d_u$ 表示直径上一点 $u$ 在不经过直径的情况下,到某个非直径上点的最远距离。设直径的点集为 $l$,起点为 $s$, 终点为 $t$。那么答案就是

但是其实里面的最后一项 $\max_{v\in \mathrm{path}(i,j)} \\{ d_v \\}$ 可以被换成 $\max_{v\in l} \\{ d_v \\}$。原因是考虑当前枚举的段外一点(此处默认是在靠 $s$ 近的一侧) $w$ 的 $d_w$ 肯定会小于等于 $dist(s,w)$,而由于 $i$ 在这一段外面,所以 $dist(s,w)<dist(s,i)$ ,也就是说对答案没有贡献,可以直接忽略掉。

于是最后就可以 $O(n)$ 做了。

然后先上一下 $rmq$ 的版本:

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
void dfs(int n, int fa){
d[n] = 0, pre[n] = 0 ;
for (int k = head[n] ; ~k ; k = next(k)){
if (to(k) == fa) continue ;
dfs(to(k), n) ;
if (d[to(k)] + val(k) > d[n])
d[n] = d[to(k)] + val(k), pre[n] = to(k) ;
}
}
void do_do(int u, int fa){
for (int k = head[u] ; ~k ; k = next(k)){
if (to(k) == fa) continue ;
do_do(to(k), u) ;
if (vis[to(k)]) continue ;
d[u] = max(d[to(k)] + val(k), d[u]) ;
}
}
int query(int l, int r){
int k = 0 ;
if (l == r) return d[l] ;
while ((1 << k) <= r - l) k ++ ;
k -- ; return max(f[l][k], f[r - (1 << k)][k]) ;
}
int main(){
int u, v, w, n ;
cin >> N >> S, cnt = -1 ;
memset(head, -1, sizeof(head)) ;
for (int i = 1 ; i < N ; ++ i)
scanf("%d%d%d", &u, &v, &w), add(u, v, w) ;
dfs(1, 0), n = 1, res = Inf ;
while (pre[n]) n = pre[n] ; dfs(n, 0) ;
while (pre[n]) vis[n] = 1, s[++ tot] = n, n = pre[n] ;
s[++ tot] = n, vis[n] = 1 ;
for (int i = 1 ; i <= tot ; ++ i) rev[s[i]] = i ;
memset(d, 0, sizeof(d)), do_do(n, 0) ;
for (int i = 1 ; i < tot ; ++ i)
for (int j = head[s[i]] ; ~j ; j = next(j))
if (to(j) == s[i + 1]) base[i + 1] = val(j) + base[i] ;
for (int i = 1 ; i <= tot ; ++ i) f[i][0] = d[s[i]] ;
for (int i = 1 ; i <= 20 ; ++ i)
for (int j = 1 ; j + (1 << i) <= tot + 1 ; ++ j)
f[j][i] = max(f[j][i - 1], f[j + (1 << i - 1)][i - 1]) ;
for (int i = 1 ; i <= tot ; ++ i) ans = max(ans, d[i]) ;
for (int r = 1, l = 1 ; r <= tot ; ++ r){
while (base[r] - base[l] > S) ++ l ; //cout << base[tot] << " " ;
res = min(res, max(max(base[l], base[tot] - base[r]), query(l, r))) ;
}
cout << res << endl ;
return 0 ;
}

然后是另一个版本:

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
il int Min(const int & a, const int & b){ return a < b? a : b ; }
il int Max(const int & a, const int & b){ return a > b? a : b ; }
int main(){
int u, v, w, n ;
fread(ch, 1, ch_top, stdin) ;
N = read(), S = read() ;
for (int i = 1 ; i < N ; ++ i)
u = read(), v = read(), w = read(), add(u, v, w) ;
dfs(1, 0), n = 1 ;
while (pre[n])
n = pre[n] ; dfs(n, 0) ;
while (pre[n])
vis[n] = 1, s[++ tot] = n, n = pre[n] ;
s[++ tot] = n, vis[n] = 1 ;
memset(d, 0, sizeof(d)), do_do(n, 0) ;
for (int i = 1 ; i < tot ; ++ i)
for (int j = head[s[i]] ; j ; j = next(j))
if (to(j) == s[i + 1]) base[i + 1] = val(j) + base[i] ;
for (int i = 1 ; i <= tot ; ++ i) ans = Max(ans, d[s[i]]) ; res = ans ;
for (int r = 1, l = 1 ; r <= tot ; ++ r){
while (base[r] - base[l] > S) ++ l ;
res = Min(res, Max(Max(base[l], base[tot] - base[r]), ans)) ;
}
write(res) ; fwrite(ch, 1, now_w - ch, stdout) ; return 0 ;
}

总结

  • 程序猿的生命大多葬送给了调试。