题目链接

LOJ3213

题目概括

给定一棵大小为$n$的树,求每条边被断掉之后得到的两个子树的重心编号之和。

数据范围:$n\leq 3\times 10^5$

思路要点

考虑一种非常暴力的做法,每次枚举每一条边$(u,v)$,然后暴力寻找重心的位置。

在考虑优化这个过程。

我们根据重心的性质,考虑用倍增在$Log_2n$的时间计算出答案。

那么需要转化当前节点的重链,维护重儿子和次重儿子,就可以了。

时间复杂度 $O(nLog_2n)$

代码

#include <bits/stdc++.h>
#define For(i,s,t) for(int i=s;i<=t;i++)

using namespace std;

const int N = 3e5 + 5;
const int LOG = 19;

vector<int> g[N];
int n;
int siz[N], son[N], par[N];
int ft[N][LOG + 1];

void solve() {
  cin >> n;
  
  auto init = [&]() {
    memset(siz, 0, sizeof siz);
    memset(son, 0, sizeof son);
    memset(par, 0, sizeof par);
    For (i, 1, n) {
      g[i].clear();
    }
  }; 
  
  init();
  For (i, 1, n - 1) {
    int u, v; 
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  function<void(int u, int fa)> dfsPre;
  dfsPre = [&](int u, int fa) {
    son[u] = 0, siz[u] = 1, par[u] = fa; 
    for (auto v : g[u]) {
      if (v != fa) {
        dfsPre(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) {
          son[u] = v; 
        }
      }
    }
    ft[u][0] = son[u];
    For (i, 1, LOG) {
      ft[u][i] = ft[ft[u][i - 1]][i - 1];
    }
  };
  dfsPre(1, 0);
  long long ans = 0;
  
  function<void(int u, int fa)> dfs;
  dfs = [&](int u, int fa) {
    function<void(int, int)> update = [&](int rt, int lim) {
      for (int i = LOG; i >= 0; i--) {
        if (ft[rt][i] && siz[ft[rt][i]] * 2 >= lim) {
          rt = ft[rt][i];
        }
      }
      ans += rt;
      if (siz[rt] * 2 == lim) {
        ans += par[rt];
      } 
    };
    
    int mxs = 0, sdx = 0;
    for (auto v : g[u]) {
      if (siz[v] > siz[mxs]) {
        sdx = mxs, mxs = v;
      } else if (siz[v] > siz[sdx]) {
        sdx = v; 
      }
    }
    for (auto v : g[u]) {
      if (v != fa) {
        update(v, siz[v]);
        siz[u] -= siz[v];
        ft[u][0] = (v == mxs ? sdx : mxs); 
        For (i, 1, LOG) {
          ft[u][i] = ft[ft[u][i - 1]][i - 1]; 
        } 
        update(u, siz[u]);
        par[u] = v, siz[v] += siz[u]; 
        dfs(v, u);
        siz[v] -= siz[u], siz[u] += siz[v];
      }
    }
    ft[u][0] = son[u];
    For (i, 1, LOG) {
      ft[u][i] = ft[ft[u][i - 1]][i - 1];
    }
    par[u] = fa;
  };
  
  dfs(1, 0);
  cout << ans << '\n';
}

int main() {
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  freopen("centroid.in", "r", stdin);
  freopen("centroid.out", "w", stdout); 
#endif
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0; 
}
最后修改:2020 年 03 月 16 日 05 : 17 PM
如果觉得我的文章对你有用,请随意赞赏