首页 > 编程学习 > NC15033 小G有一个大树

NC15033 小G有一个大树

发布时间:2022/9/20 13:50:37

题目

  • 原题地址:小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;
}
  • 参考题解
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号