树的重心

ACM模版

---

添加于2017.3.8日

树的重心

typedef long long ll; typedef pair<int, int> pll; const int INF = 0x3f3f3f3f; const int MAXN = 100000 + 10; int n; /* 树的重心 * 初始化 vis[] son[] 为 0 * 初始化 sz 为 INF */ int zx, sz; int son[MAXN], vis[MAXN]; vector<pll> edge[MAXN]; void init() { for (int i = 1; i <= n; i++) { edge[i].clear(); } memset(vis, 0, sizeof(vis)); sz = INF; zx = -1; } void dfs(int r) { vis[r] = 1; son[r] = 0; int tmp = 0; for (int i = 0; i < edge[r].size(); i++) { int v = edge[r][i].second; if (!vis[v]) { dfs(v); son[r] += son[v] + 1; tmp = max(tmp, son[v] + 1); } } tmp = max(tmp, n - son[r] - 1); if (tmp < sz) { zx = r; sz = tmp; } }