846. 树的重心

重心"/>

846. 树的重心

输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例：

4

分析：因为有n-1条边，所以每个点必然会连接到其他点，不存在孤立点，因此，我们从1-n任意点开始dfs都是可以的，因为无论怎么样，每个点都必然会被遍历。

我的思路：假设一个结点被删除，那么会出现三块连通块，分别是该点的左子树，右子树，和其他。然而要求左子树和右子树的节点数有点困难，因此我的思路是错误的。

但求左右子树的总节点数是可以的

因此插入一个极其重要的知识点：dfs遍历树，是可以知道其子树的节点数的

如正确答案所示，这里的dfs并不是像其他题一样，为了找答案而遍历，找到答案就return。

而是在遍历的过程中不断找最优答案，很多树上dfs都是这样。

然后还有一点疑惑，int s = dfs(x);  res = max(res, s); res = max(res, n - sum);

比如当前cur为4。那s是以4为根结点的树的节点数，n-sum是其余树，为啥要这样比较？如果这样的话是在删哪一个结点？这哪里有删的动作啊？按照我的理解，应该是当前删cur呀

算法写的很像在删除cur，实则不然。

res = max(res, s)是在跟以4为根节点的树作比较，可以假装这时候是在删1

而res = max(res, n - sum)是在跟其余树作比较，可以假装这时候在删4

很难想到

但代码总归能遍历到所有情况

int n, vis[N], ans = inf;
vector<vector<int>> v(1e5 + 10);int dfs(int cur) {//以cur为根，与左右子树的节点个数（包括cur）vis[cur] = 1;int sum = 1, res = 0;for (auto x : v[cur]) {if (!vis[x]) {int s = dfs(x);sum += s;res = max(res, s);}}res = max(res, n - sum);ans = min(ans, res);return sum;
}
signed main() {cin >> n;for (int i = 1; i < n; i++) {int a, b; cin >> a >> b;v[a].push_back(b);v[b].push_back(a);}dfs(1);cout << ans;return 0;
}