1. Preface

The diameter of a tree is a small part of a tree, but it has important applications.

Pre knowledge: the basic knowledge of the tree.

2. Detailed explanation

Example: SP1437 PT07Z - Longest path in a tree

2.1 definitions

Tree diameter: the longest path on a tree is called the diameter of the tree.

For example, in the following tree, the path with edge weight 1 is the diameter of the tree.

It should be noted that there is more than one diameter of this tree, but generally, we only take one of them as the diameter of this tree.

2.2 calculation method

So how to find the diameter of the tree?

There are two methods: DFS and tree DP.

2.2.1 DFS solution

The general steps of the algorithm are as follows:

• First, take a random point and do DFS again to find the farthest point that this point can reach.
• Then DFS again from this point to find the farthest point that this point can reach.
• The path between the two points is the diameter of the tree.

The steps are simple and easy to understand, so why is this algorithm correct?

The following proof assumes that the edge weight is greater than 0.

Counter evidence method:

Assuming that there is a path longer than the path we calculated in the graph, then this path is the diameter of the tree.

Let the path we find be \ (AB \) and the real diameter be \ (CD \).

There are two situations:

1. The diameter intersects or partially coincides with the path we find.

Then, according to the above algorithm, when we find the point \ (A \) for the first time, there must be \ (AE > CE \).

Similarly, there are \ (AE + EF + FB > AE + EF + FD \).

Consider bringing \ (AE > CE \) into the above inequality, including \ (AE + EF + FB > CE + EF + FD \), which is inconsistent with the diameter of \ (CD \), so the above situation is not tenable.

1. The diameter does not coincide with the path we found.

Then \ (CF + FD > CF + EF + EB \), so \ (FD > EF + EB \), there is \ (FD > EB \).

However, according to our algorithm steps, \ (EB > EF + FD \), there is \ (EB > FD \).

There are contradictions, so the original assumption is wrong.

To sum up, \ (AB \) must be diameter.

So why does the proof have to have an edge weight greater than 0?

This is because if the edge weight is less than 0, the \ (a>b+c\rightarrow a>c\) of all the above proofs may not be true.

At the same time, it also reveals that the diameter of DFS tree must have all edge weights greater than 0.

Advantages of DFS: it can record the diameter of the tree, that is, it can record the path completely.

Disadvantages of DFS: it cannot handle trees with negative edge weight.

2.2.2 tree DP solution

This requires a certain tree DP foundation. Of course, there is no foundation and no problem.

Consider setting \ (f1_i,f2_i \) to represent the maximum value and the second maximum value of the path from the (I \) node to the leaf node respectively.

Then the design state transition equation:

Let the current point be \ (u \), the child node of the current enumeration be \ (v \), and the edge weight be \ (val \), then there is the following equation:

• If \ (f1_v + Val > f1_ \), then \ (f2_ \ leftarrow f1_, f1_ \ leftarrow f1_v + val \).
• Otherwise, \ (f2_ = \ Max \ {f2_, f1_v + val \} \).

The transfer equation is simple and easy to understand qwq

The final answer is \ (\ max\{f1_i+f2_i|i \in [1,n] \} \).

So this approach is obvious, because it is DP idea, which can deal with trees with negative edge weight.

Advantages of tree DP: it can deal with trees with negative edge weight.

Disadvantage of tree DP: path cannot be recorded.

2.3 code

The codes of the two methods are as follows (Solve_dfs is DFS method and Solve_DP is tree DP method):

/*
========= Plozia =========
    Author:Plozia
    Problem:SP1437 PT07Z - Longest path in a tree
    Date:2021/4/27
    Another:Tree diameter template problem
========= Plozia =========
*/

#include <bits/stdc++.h>

typedef long long LL;
const int MAXN = 1e4 + 10;
int n, Head[MAXN], cnt_Edge = 1, f[MAXN], ans, root, f1[MAXN], f2[MAXN];
struct node { int Next, to, val; } Edge[MAXN << 1];

int read()
{
    int sum = 0, fh = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
    return sum * fh;
}
int Max(int fir, int sec) { return (fir > sec) ? fir : sec; }
void add_Edge(int x, int y, int z) { ++cnt_Edge; Edge[cnt_Edge] = (node){ Head[x], y, z }; Head[x] = cnt_Edge; }

void dfs(int now, int father)
{
    if (f[now] > ans) { ans = f[now]; root = now; }
    for (int i = Head[now]; i; i = Edge[i].Next)
    {
        int u = Edge[i].to;
        if (u == father) continue ;
        f[u] = f[now] + Edge[i].val;
        dfs(u, now);
    }
}

void Solve_DFS()
{
    root = 1;
    f[root] = 0; dfs(root, 0); ans = 0;
    f[root] = 0; dfs(root, 0);
    printf("%d\n", ans);
}

void DP(int now, int father)
{
    for (int i = Head[now]; i; i = Edge[i].Next)
    {
        int u = Edge[i].to;
        if (u == father) continue ;
        DP(u, now);
        if (f1[u] + Edge[i].val > f1[now]) { f2[now] = f1[now]; f1[now] = f1[u] + Edge[i].val; }
        else { f2[now] = Max(f2[now], f1[u] + Edge[i].val); }
    }
}

void Solve_DP()
{
    DP(1, 0);
    for (int i = 1; i <= n; ++i) ans = Max(ans, f1[i] + f2[i]);
    printf("%d\n", ans);
}

int main()
{
    n = read();
    for (int i = 1; i < n; ++i)
    {
        int u = read(), v = read();
        add_Edge(u, v, 1); add_Edge(v, u, 1);
    }
    // Solve_DFS(); return 0;
    Solve_DP(); return 0;
}

3. Summary

Tree diameter: the longest path on the tree.

Solution:

• DFS solution twice.
  • Advantage: the path can be recorded.
  • Disadvantages: negative edge weight cannot be handled.
• Tree DP solution.
  • Advantages: negative edge weight can be handled.
  • Disadvantages: cannot handle paths.