题目

• 原题地址：小G有一个大树
• 题目编号：NC15033
• 题目类型：DP、树形DP
• 时间限制：C/C++ 1秒，其他语言2秒
• 空间限制：C/C++ 32768K，其他语言65536K

1.题目大意

• 小G想要把自己家院子里的橘子树搬到家门口（QAQ。。就当小G是大力水手吧）
• 可是小G是个平衡性灰常灰常差的人，他想找到一个这个橘子树的平衡点。
• 怎么描述这棵树呢。。。就把它看成由一个个节点构成的树吧。结点数就代表树重。

2.题目分析

• 树形dp记录每个点下面的节点个数，求出删除一个点时的最大子树大小，比较后得到答案。
• m不能设为全局变量qwq

3.题目代码

#include<bits/stdc++.h>

using namespace std;

int n,f[1003],u,v,a1=1e9,a2=1e9;
vector<int> g[1003];
void dfs(int u,int p){
    f[u] = 1;int m = 0;
    for(auto k:g[u]) if(k!=p) dfs(k,u),f[u]+=f[k],m=max(m,f[k]);m=max(m,n-f[u]);
    if(m<a2)a2=m,a1=u;else if(m==a2&&a1>u)a1=u;
}
int main() {
    cin >> n;
    for(int i=1;i<n;i++) cin >> u >> v,g[u].push_back(v),g[v].push_back(u);
    dfs(1,0), cout << a1 << ' ' << a2 << endl;
}

• 参考题解