Блог пользователя electro177

Diameter of a tree
Автор electro177, история, 3 года назад, По-английски 

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

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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.

→ Ответить