首页 > 代码库 > SGU 195. New Year Bonus Grant
SGU 195. New Year Bonus Grant
时间限制：0.75s
空间限制：4M
题意：
在一颗树（最多500000个节点）中，可以对节点染色，但是一个节点染了色后，它的父节点和兄弟节点都不能再染了，求最大的染色节点数，并输出所有染色节点。
Solution：
一开始写了一个树形DP
后来看到有人说题目的输入是从上到下的。。。直接倒过来贪心就好了。ORZ
代码：
#include <iostream>#include <cstdio>using namespace std;const int INF = 510000;int f[INF], vis[INF], ans[INF], tol, n;int main() { scanf ("%d", &n); for (int i = 1; i < n; i++) scanf ("%d", &f[i + 1]); for (int i = n; i > 1; i--) if (!vis[i] && !vis[f[i]]) { vis[f[i]] = vis[i] = 1; ans[++tol] = i; } printf ("%d\n", tol * 1000); for (int i = tol; i > 0; i--) printf ("%d ", ans[i]); return 0;}
SGU 195. New Year Bonus Grant
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。