首页 > 小G有一个大树
开通博客写题解
头像 学不完了
发表于 2020-08-11 16:47:13
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL INF = 0x3f3f3f3f; cons 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 ______________________
发表于 2020-08-12 19:03:13
题目不描述了，参考了大佬的代码，具体思路写在代码里面 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6+6; int n; vector<int> g 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 瑜画
发表于 2020-08-07 19:58:46
初学树形dp，看着雨聚聚的PPT上思路搞出来了。。。题目意思：找到一个割点，树将被割成两个部分，找到最大的连通块。 状态转移方程：F[i]=max(max(tot[k]),n-tot[i]] （k是i的子树）然后dfs的时候把状态转移方程带进去就好了，注意每一次都得把自己这个点算上。另外，为了防止对 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 在刷题的单身狗很开心
发表于 2023-10-19 16:48:48
对于某个节点来说，如果该节点删除那么就会形成他儿子节点全部独立成一棵树和他父亲节点的那棵树。 那么状态转移方程：dp[i] = (total-f[i], (所有儿子节点最大的那个)f[u]) 对于求某个节点下有多少节点来说是一个简答树状dp问题。 f[i] = 1+(所有儿子节点)f[u]; 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 lifehappy
发表于 2020-08-09 18:24:21
小G有一个大树 思路 树的重心，经典的问题了，我们只要用一个数组来统计当前节点的儿子个数即可，然后按照题目更新答案。 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include < 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 sunsetcolors
发表于 2020-08-13 14:58:32
小G有一个大树 题目地址： https://ac.nowcoder.com/acm/problem/15033 基本思路： 树的重心模板题，我们顺便来复习一下重心的性质： 树的重心的定义就是题意：找到一个点,其所有的子树中最大的子树节点数最少。 我们再来看下百度百科里树的重心的性质： 树中 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 mujinSong
发表于 2021-09-28 18:27:57
看很多人题解的dfs还要传上一个节点,还有考虑一堆,蒟蒻给像我一样的蒟蒻讲一讲侥幸过的代码 vector<int> r[1001]; int w[1001]; int dp[1001]; void dfs(int x) { if (r[x].empty()) { 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 威风镰鼬
发表于 2021-06-16 12:50:38
思路 题目都没看懂就莫名其妙A了，“如果结点数相同输出编号小的”，是指平衡点的编号吗？下面题解是按照这样理解的。我先讲一下做题思路吧，数据规模很小，1e3，所以可以把每一个节点当作根去找树的最大深度，最大深度最小的第一个节点可以作为平衡点。找到平衡点之后再来一个push_up对他每一个子节点计算树的 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Z_L_G
发表于 2025-05-14 23:26:40
题意 对于一棵树，我们希望找到一个点，使得删除这个点之后，最大子树的结点数最小 以边的形式输入，输出被删除的点的编号和删除后最大子树的结点数 思路 考虑用无根树描述，对于树的某一个结点，删掉后，整棵树变为两部分 这个结点的父亲所属的树 这个结点的若干子树 故另表示删除这个点后最大子树结点 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Ray.C.L
发表于 2020-08-08 12:47:02
思路：找平衡点，删掉一个点后子树节点差最小的就是平衡点，size[i]表示以i节点给根的子节点的个数，f[i]表示删除i节点后最大联通块的节点数，v代表i的子节点，f[i]=max(max(size[v]),n-size[i]),当i节点作为平衡点删去后，留下的最大联通块的节点数要么是他上面的树的节 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”