#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f;
cons
展开全文
题目不描述了，参考了大佬的代码，具体思路写在代码里面 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
int n;
vector<int> g
展开全文
初学树形dp，看着雨聚聚的PPT上思路搞出来了。。。题目意思：找到一个割点，树将被割成两个部分，找到最大的连通块。 状态转移方程：F[i]=max(max(tot[k]),n-tot[i]] （k是i的子树）然后dfs的时候把状态转移方程带进去就好了，注意每一次都得把自己这个点算上。另外，为了防止对
展开全文
利用树的重心这一性质
以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const in
展开全文
对于某个节点来说，如果该节点删除那么就会形成他儿子节点全部独立成一棵树和他父亲节点的那棵树。
那么状态转移方程：dp[i] = (total-f[i], (所有儿子节点最大的那个)f[u])
对于求某个节点下有多少节点来说是一个简答树状dp问题。
f[i] = 1+(所有儿子节点)f[u];
展开全文
小G有一个大树 思路 树的重心，经典的问题了，我们只要用一个数组来统计当前节点的儿子个数即可，然后按照题目更新答案。 代码 /*
Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <
展开全文
小G有一个大树 题目地址： https://ac.nowcoder.com/acm/problem/15033 基本思路： 树的重心模板题，我们顺便来复习一下重心的性质： 树的重心的定义就是题意：找到一个点,其所有的子树中最大的子树节点数最少。 我们再来看下百度百科里树的重心的性质： 树中
展开全文
看很多人题解的dfs还要传上一个节点,还有考虑一堆,蒟蒻给像我一样的蒟蒻讲一讲侥幸过的代码 vector<int> r[1001];
int w[1001];
int dp[1001];
void dfs(int x) {
if (r[x].empty()) {
展开全文
思路 题目都没看懂就莫名其妙A了，“如果结点数相同输出编号小的”，是指平衡点的编号吗？下面题解是按照这样理解的。我先讲一下做题思路吧，数据规模很小，1e3，所以可以把每一个节点当作根去找树的最大深度，最大深度最小的第一个节点可以作为平衡点。找到平衡点之后再来一个push_up对他每一个子节点计算树的
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
