electro177's blog

By electro177, history, 3 years ago, In English

const int mxN = 2e5; int n, d[mxN], ans; vector<int> adj[mxN]; void dfs(int u = 0, int p = -1) { for (int v : adj[u]) { if (v == p) continue; dfs(v, u); ans = max(d[u] + d[v] + 1, ans); d[u] = max(d[u], d[v] + 1); } }

ans gives the diameter of the tree .It is not that trivial to understand for me.can someone explain please explain how the code works

  • Vote: I like it
  • -10
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Diameter is the longest path. If you root the tree then every path has a single vertex that is closest to the root (u). The longest paths go from u to two of its deepest children. We therefore keep track of the depth of the deepest child of u as d[u]. It remains to make sure that all paths are indeed considered, which determines the order of the statements in the dfs.