网站平台建设多少钱,wordpress 文章底部,企业网站的搜索引擎推广与优化,wordpress不能自定义菜单有一棵 n n n 个节点的以 1 1 1 号点为根的有根树。现在可以对这棵树进行若干次操作#xff0c;每一次操作可以选择树上的一个点然后删掉连接这个点和它的儿子的所有边。
现在我们想知道对于每一个 k k k ( 1 ≤ k ≤ n 1≤k≤n 1≤k≤n)#xff0c;最少需要多少次操作能…有一棵 n n n 个节点的以 1 1 1 号点为根的有根树。现在可以对这棵树进行若干次操作每一次操作可以选择树上的一个点然后删掉连接这个点和它的儿子的所有边。
现在我们想知道对于每一个 k k k ( 1 ≤ k ≤ n 1≤k≤n 1≤k≤n)最少需要多少次操作能让图中恰好存在 k k k 个联通块。
输入格式
第一行输入一个正整数 n n n。
第二行输入 n − 1 n−1 n−1 个整数 f 1 , f 2 , . . . , f n − 1 f_1,f_2,...,f_{n−1} f1,f2,...,fn−1 f i f_i fi 表示 i 1 i1 i1 号点的父亲保证 1 ≤ f i ≤ i 1≤f_i≤i 1≤fi≤i。
输出格式
输出 n n n 个整数第 i i i 个数表示 k i ki ki 时的答案如果无法让图中恰好存在 i i i 个联通块则输出 -1。
样例输入1
6
1 2 1 1 2样例输出1
0 -1 1 1 -1 2数据规模
共 10 10 10 个测试点。
测试点 1 , 2 , 3 1,2,3 1,2,3 满足 n ≤ 20 n≤20 n≤20。
测试点 4 , 5 , 6 4,5,6 4,5,6 满足 n ≤ 100 n≤100 n≤100。
对于所有数据满足 1 ≤ n ≤ 3000 1≤n≤3000 1≤n≤3000。
解题思路
对于一棵树来说删去任意一条边都会使连通块数目 1 1 1。
那么要判断能否得到 k k k个连通块我们只需要判断能否恰好删去 k − 1 k-1 k−1条边。
题目要求操作为删除一个节点与子节点之间的所有边。
那么统计每个节点的子节点数目然后就变为了01背包可行性问题
每一个节点都是一个物品问能否恰好装满容量为 k − 1 k-1 k−1的背包
for (int i 1; i n; i) {//尝试每一个物品for (int j 0; j n; j) {//尝试新的重量组合if (j - items[i] 0)ans[i][j] ans[i - 1][j] || ans[i - 1][j - items[i]];elseans[i][j] ans[i - 1][j];}
}以上我们只是检验了可行性问题但是题目中还有另外一个要求操作次数最少。
因为在物品组合中没有先后顺序所以我们可以通过物品组合中的物品数量来确定操作次数。
只有新的操作次数小于旧的操作次数的时候我们才进行更新。
for (int i 1; i n; i) {//尝试每一个物品for (int j 0; j n; j) {//尝试新的重量组合if (j - items[i] 0 ans[i - 1][j] ans[i - 1][j - items[i]])ans[i][j] min(ans[i - 1][j], ans[i - 1][j - items[i]] 1);else if (ans[i - 1][j])ans[i][j] ans[i - 1][j];else if (j - items[i] 0 ans[i - 1][j - items[i]])ans[i][j] ans[i - 1][j - items[i]];}
}注1以上代码段中ans中元素的含义发生了变化可行/不可行 - 物品数量
2为了与不存在的组合ans[i][j] 0相区分我们为所有存在的组合物品数量添加偏置bias也就是说物品数量 ans[i][j] - bias。
以上代码的空间复杂度、时间复杂度均可以接受可以AC接下来是优化部分qwq。
因为嫌弃这个算法的空间复杂度所以我们对其进行优化压缩到二维数组
for (int i 1; i n; i) {//尝试每一个物品for (int j 0; j n; j) {//尝试新的重量组合if (j - items[i] 0 ans[(i - 1) % 2][j] ans[(i - 1) % 2][j - items[i]])ans[i % 2][j] min(ans[(i - 1) % 2][j], ans[(i - 1) % 2][j - items[i]] 1);else if (ans[(i - 1) % 2][j])ans[i % 2][j] ans[(i - 1) % 2][j];else if (j - items[i] 0 ans[(i - 1) % 2][j - items[i]])ans[i % 2][j] ans[(i - 1) % 2][j - items[i]];}
}还是嫌弃继续压压缩到一维数组
for (int i 1; i n; i) {//尝试每一个物品for (int j n; j items[i]; j--) {//尝试新的重量组合if (j - items[i] 0 ans[j] ans[j - items[i]])ans[j] min(ans[j], ans[j - items[i]] 1);else if (ans[j]) ans[j] ans[j];else if (j - items[i] 0 ans[j - items[i]])ans[j] ans[j - items[i]] 1;}
}然后我们删除一些无用的部分
for (int i 1; i n; i) {//尝试每一个物品for (int j n; j items[i]; j--) {//尝试新的重量组合if (ans[j] ans[j - items[i]]) ans[j] min(ans[j], ans[j - items[i]] 1);else if (ans[j - items[i]]) ans[j] ans[j - items[i]] 1;}
}嗯好看多了qwq。
最后AC代码如下
#include iostream
using namespace std;
const int max_n 3000;int ans[max_n 1], n;
int items[max_n 1];int main() {cin n;int fa;for (int i 1; i n; i) {cin fa;items[fa];}int bias 1;ans[0] bias;for (int i 1; i n; i) {//尝试每一个物品for (int j n; j items[i]; j--) {//尝试新的重量组合if (ans[j] ans[j - items[i]]) ans[j] min(ans[j], ans[j - items[i]] 1);else if (ans[j - items[i]]) ans[j] ans[j - items[i]] 1;}}cout 0;for (int i 2; i n; i) {cout ans[i - 1] - bias;}return 0;
}
