树学

Solution

题目求最小的, 考虑找树的重心, 其所有的子树中最大的子树节点数最少。
能保证每一个子树中的点深度和是最小的, 然后从重心开始给每个点赋深度, 求一下和即可。
那么问题就转化为如何求重心, 这是树形dp的一个经典应用, 用cnt[i] 表示 i 点的子树的节点
有 dp[u] = max(dp[u], n - cnt[u]) 找一下 dp[u] 的最小值即是重心
然后进行 bfs 一遍赋深度即可
注意这道题 vector 会超 1s, 比赛的时候时限只给 1s , 后面改成 2s。
比赛时卡了vector, 建议使用链式前向星。

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const ll mod = 998244353;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
const int N = 1e6 + 5;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
struct Edge{
  int v, nextz;
}edge[N << 1];
int head[N], tot;
void addedge(int u, int v){
  edge[tot].v = v;
  edge[tot].nextz = head[u];
  head[u] = tot++;
}
int n;
int dp[N], cnt[N];
void dfs(int x, int fa){
    dp[x] = 0, cnt[x] = 1;
    for(int i = head[x]; i != -1; i = edge[i].nextz){
        int v = edge[i].v;
        if(v == fa){
            continue;
        }
        dfs(v, x);
        dp[x] = max(dp[x], cnt[v]);
        cnt[x] += cnt[v]; 
    }
    dp[x] = max(dp[x], n - cnt[x]);
}
int dep[N];
bool vis[N];
void bfs(int root){
  queue<int> q;
  q.push(root);
  dep[root] = 0;
  while(!q.empty()){
    int now = q.front();
    q.pop();
    if(vis[now]) continue;
    vis[now] = 1;
    for(int i = head[now]; i != -1; i = edge[i].nextz){
      int v = edge[i].v;
      if(!vis[v]){
        dep[v] = dep[now] + 1;
        q.push(v);
      }
    }
  }
}
int main(){
  memset(head, -1, sizeof(head));
  cin >> n;
  for(int i = 1; i <= n - 1; i++){
    int u, v;
    cin >> u >> v;
    addedge(u, v);
    addedge(v, u);
  }
  dfs(1, -1);
  int ans = *min_element(dp + 1, dp + 1 + n);
  int root = -1;
  for(int i = 1; i <= n; i++){
    if(ans == dp[i]){
      root = i;
      break;
    }
  }
  bfs(root);
  ans = 0;
  for(int i = 1; i <= n; i++) ans += dep[i];
  cout << ans << "\n";
  return 0;
}

Accumulation Degree

Solution

上完课再来