树的重心
定义
树的重心指的是删掉节点\(u\)后，剩余的所有连通块中，节点数量最多的那个连通块的大小。
定理
- 深度之和最小的点就是重心
- 所有子树的大小不超过 \(\frac{n}{2}\)
解决方法
- 就是换根\(dp\)，\(dp\)转移式为
\[dp_v = dp_u + n - sz_v * 2;
\]
- 一个只需要一次\(dfs\)的好方法（That's good idea）
我们知道，当把节点 \(u\) 删除时，他会分成若干部分：以他直接相连的子儿子为根的若干子树
那么我们只需要算他子树中的最大的子树，即可，而另一部分，可以用 \(n - sz_u\) 表示大小，取最大值即可。
点击查看代码
int n;
vector<int> g[N];
vector<int> ans;
int Ans = 1e18;
int sz[N];void dfs(int u, int fa) {sz[u] = 1;int maxn = 0;for (auto v : g[u]) {if (v == fa) continue;dfs(v, u);sz[u] += sz[v], maxn = max(maxn, sz[v]);}maxn = max(maxn, n - sz[u]);if (maxn < Ans) Ans = maxn, ans.clear(), ans.push_back(u);else if (maxn == Ans) ans.push_back(u);
}
树的同构
感觉上难，其实十分的简。
我们以一道比较简单的紫题为例（这种紫随手切，但被hack了qwq）
[JSOI2016] 独特的树叶
你为什么不开，是不信任我吗？QAQ
算了，话不多说，因为说多了容易成废话。
解法
树上哈希。自己可以先去了解一下。
我们需要用到一个随机数，就用mt19937_64 rd(time(nullptr));了！
我们为了不被哈希冲突，所以用一个奇奇怪怪的函数！
ull f(ull x) {x ^= mask, x ^= x << 13, x ^= x >> 7, x ^= x << 17, x ^= mask;return x;
}
这个函数降低了哈希冲突的概率！
后面简单了，直接给代码吧！
点击查看代码
int n;
ull ans[N], G[N];
vector<int> g[N];mt19937_64 rd(time(nullptr));const ull mask = rd();ull f(ull x) {x ^= mask, x ^= x << 13, x ^= x >> 7, x ^= x << 17, x ^= mask;return x;
}void dfs1(int u, int fa) {ans[u] = 1;for (auto v : g[u]) {if (v == fa) continue;dfs1(v, u);ans[u] += f(ans[v]);}
}set<ull> s;void dfs2(int u, int fa) {for (auto v : g[u]) {if (v == fa) continue;G[v] = ans[v] + f(G[u] - f(ans[v]));s.insert(f(G[v]) + 1);dfs2(v, u);}
}
最后的答案自己想想！