题解 - 南师大算法竞赛域 - Vijos

0

19220448 董文杰 (董文杰) LV 9 @ 1 年前

算法：换根dp | BFS

题意：给定一棵树，现在需要选择其中的一个结点为根节点，使得深度和最大。深度的定义是以每个结点到树根所经历的结点数

思路：
暴力：

显然可以直接遍历每一个结点，计算每个结点的深度和，然后取最大值即可

时间复杂度： $O(n^2)$
优化：

先看图：

图示
我们可以发现，对于当前的根结点 fa，我们选择其中的一个子结点 ch，将 ch 作为新的根结点（如右图）。那么对于当前的 ch 的深度和，我们可以借助 fa 的深度和进行求解。我们假设以 ch 为子树的结点总数为 x，那么这 x 个结点在换根之后，相对于 ch 的深度和，贡献了 -x 的深度；而对于 fa 的剩下来的 n-x 个结点，相对于 ch 的深度和，贡献了 n-x 的深度。于是 ch 的深度和就是 fa的深度和 -x+n-x，即
dep[ch] = dep[fa]-x+n-x = dep[fa]+n-2*x
于是我们很快就能想到利用前后层的递推关系， $O(1)$ 的计算出所有子结点的深度和
代码实现：我们可以先计算出 base 的情况，即任选一个结点作为根结点，然后基于此进行迭代计算。在迭代计算的时候需要注意的点就是在一遍 dfs 计算某个结点的深度和 dep[root] 时，如果希望同时计算出每一个结点作为子树时，子树的结点数，显然需要分治计算一波。关于分治的计算我熟练度不够高，~~特此标注一下debug了3h的点~~：即在递归到最底层，进行回溯计算的时候，需要注意不能统计父结点的结点值（因为建的是双向图，所以一定会有从父结点回溯的情况），那么为了避开这个点，就需要在 $O(1)$ 的时间复杂度内获得当前结点的父结点的编号，从而进行特判，采用的方式就是增加递归参数 fa。
没有考虑从父结点回溯的情况的dfs代码
void dfs(int now, int depth) {
  if (!st[now]) {
      st[now] = true;
      dep[root] += depth;
      for (auto& ch: G[now]) {
          dfs(ch, depth + 1);
          cnt[now] += cnt[ch];
      }
  }
}
Copy
考虑了从父结点回溯的情况的dfs代码
void dfs(int now, int fa, int depth) {
  if (!st[now]) {
      st[now] = true;
      dep[root] += depth;
      for (auto& ch: G[now]) {
          dfs(ch, now, depth + 1);
          if (ch != fa) {
              cnt[now] += cnt[ch];
          }
      }
  }
}
Copy
时间复杂度： $O(2n)$

暴力代码：

const int N = 500010;

int n;
vector<int> G[N];
int st[N], dep[N];

void dfs(int id, int now, int depth) {
    if (!st[now]) {
        st[now] = 1;
        dep[id] += depth;
        for (auto& node: G[now]) {
            dfs(id, node, depth + 1);
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    int res = 0;

    for (int i = 1; i <= n; i++) {
        memset(st, 0, sizeof st);
        dfs(i, i, 1);
        res = max(res, dep[i]);
    }

    cout << res << "\n";
}

优化代码：

const int N = 500010;

int n, dep[N], root = 1;
vector<int> G[N], cnt(N, 1);
bool st[N];

// 当前结点编号 now，当前结点的父结点 fa，当前结点深度 depth
void dfs(int now, int fa, int depth) {
    if (!st[now]) {
        st[now] = true;
        dep[root] += depth;
        for (auto& ch: G[now]) {
            dfs(ch, now, depth + 1);
            if (ch != fa) {
                cnt[now] += cnt[ch];
            }
        }
    }
}

void bfs() {
    memset(st, 0, sizeof st);
    queue<int> q;
    q.push(root);
    st[root] = true;

    while (q.size()) {
        int fa = q.front(); // 父结点编号 fa
        q.pop();
        for (auto& ch: G[fa]) {
            if (!st[ch]) {
                st[ch] = true;
                dep[ch] = dep[fa] + n - 2 * cnt[ch];
                q.push(ch);
            }
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    dfs(root, -1, 1);
    bfs();

    cout << *max_element(dep, dep + n + 1) << "\n";
}

ID: 1534
难度: 7
分类: (无)
标签: (无)
递交数: 25
已通过: 6
通过率: 24%
上传者: njnu19210225 (季润民)