思路 应该是个比较基础的换根吧...我相信我再做几个换根应该都能做出来的!令表示这个节点的联通点集的数量.那么一个很显然的一个方程就是其中是的子节点.这个点的联通点集数量就是子节点的联通点集数量的选取,以及不选取的方案数的乘积.由此我们可以的算出一个点的答案是多少.然后考虑换根,的子节点的答案怎么算
展开全文
题意：给与一棵n个节点的树，求每个点的连通点集的数量？ 思路：树形结构+换根dp[i]表示以i为根且包括i的这棵子树连通点集的数量。ans[i]表示包括i的连通点集的数量，既结果。父节点u与子节点v：dp[u]= (dp[v]+1) * dp[u];（v为u的子节点）换根时:ans[v]=((ans
展开全文
C Tree 题目地址： https://ac.nowcoder.com/acm/contest/6226/C 基本思路： 类似换根的思路，我们先只向下考虑，也就是先只考虑子树的情况。 这样我们设表示以为根的子树中联通点集的数量，那么易得如下转移方程： 然后我们要计算每个点里向上那部分点集
展开全文
//对于每一个结点，是孩子+1的乘积
//因为自己一定会取，所以孩子的集合方案就多了一个空集
//换根dp过程，把原来的父节点旋转下去
//首先将父亲结点的方案数除以这个转上去的孩子+1
//也就是说消除原来这个孩子结点的贡献
//然后把新父亲结点乘以这个新孩子结点，也就是说贡献上去
//第二次df
展开全文
根据树的性质进行两个深度优先搜索就可以了，要注意数据的范围。代码如下： #include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 1e6+10;
const long long
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
