图论（树的直径）

89 阅读 0 评论 59 点赞

我是靠谱客的博主年轻胡萝卜，这篇文章主要介绍图论（树的直径），现在分享给大家，希望可以做个参考。

一、基础

树中最远的两个结点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链（也称直径）

二、两次遍历求直径

1、从任意一个结点出发，通过bfs或者dfs对树进行一次遍历，求出与出发点距离最远的结点，记为p，这就是树的直径的一端

2、从结点p出发，通过bfs和dfs对树再进行一次遍历，求出与p距离最远的结点，记为q

3、那么p到q的路径就是树的一条直径，因为p一定是直径的一端，否则总能找到一条更长的链。在第二步遍历过程中，可以记录下来每个点第一次被访问时的前驱节点，最后从q回溯到p即可得到直径的具体方案

4、注：通过搜索不能解决负边权的问题

复制代码

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
int to[maxn << 1], nex[maxn << 1], edge[maxn << 1], head[maxn];
int cnt, n, m, r;
ll
dis[maxn], maxd, maxv;
void add(int u, int v, int w)
{
to[++cnt] = v;
edge[cnt] = w;
nex[cnt] = head[u];
head[u] = cnt;
}
void dfs(int u, int fa)
{
if (maxd < dis[u])
{
maxd = dis[u];
maxv = u;
}
for (int i = head[u]; i; i = nex[i])
{
int v = to[i];
if (fa == v)
continue;
dis[v] = dis[u] + edge[i];
dfs(v, u);
}
}
void solve()
{
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dfs(1, 0);
maxd = 0;
dis[maxv] = 0;
dfs(maxv, 0);
cout << maxd;
}

三、树形dp求直径

1、设d[x]表示从结点x出发走向以x为根的子树，能够到达的最远节点的距离，即x向下走的最长链，显然有

$d[x]= underset {1leq ileq t}{max}{d[y_i]+w(x,y_i)}$

2、那么我们可以考虑求出经过每个点x的最长链的长度f[x]，那么整个树的直径就是最大的f[x]。对于x的任意两个结点yi，yj，经过结点x的最长链的长度由四部分组成，如下

$f[x]=underset {1leq j<ileq t}{max}{d[y_i]+d[y_j]+w(x,y_i)+w(x,y_j)}$

3、当子节点枚举到i时，d[x]正好保存了从x出发向以yi为根的子树能达到的最远的结点的距离，这个距离就是 $underset {1leq j<i}{max}{d[y_j]+w(x,y_j)}$ ，所以我们先用 $d[x]+d[y_i]+w(x,y_i)$ 更新f[x]，再用 $d[y_i]+w(x,y_i)$ 更新d[x]即可

复制代码

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
int to[maxn << 1], nex[maxn << 1], edge[maxn << 1], head[maxn];
int vis[maxn];
int cnt, n, m, r;
ll ans = 0, d[maxn];
void add(int u, int v, int w)
{
to[++cnt] = v;
edge[cnt] = w;
nex[cnt] = head[u];
head[u] = cnt;
}
void dp(int u)
{
vis[u] = 1;
for (int i = head[u]; i; i = nex[i])
{
int v = to[i];
if (vis[v])
continue;
dp(v);
ans = max(ans, d[u] + d[v] + edge[i]);
d[u] = max(d[u], d[v] + edge[i]);
}
}
void solve()
{
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dp(1);
cout << ans << 'n';
}