GYM-100199C New Year Bonus Grant 贪心,树
题意
本人英文能力有限,一开始甚至没有读懂题目。
归纳以后题意大致如下:
给出一棵树,对这棵树进行染色:
如果一个点被染色,那么它的父亲儿子兄弟结点都不能再染色。
问最多能染哪些。
分析
一开始想复杂了,在往树形DP方面想,但最后打印方案这一步没想出来。
后来发现贪心的选即可。
而且题中给定了上司的结点编号一定比下属的结点编码大,这样就更方便处理了。
思路就是贪心的从叶子节点网上选。如果可以选就选。
简要证明就是选叶子必然比选其他好,因为一旦选其他结点,会导致更多的点不能被选。
int fa[maxn];
bool vis[maxn];
vector<int> res;
int main() {
freopen("grant.in", "r", stdin);
freopen("grant.out", "w", stdout);
int n = readint();
for (int i = 0; i < n - 1; i++) {
int x = readint();
fa[i + 2] = x;
}
for (int i = n; i >= 2; i--)
if (!vis[fa[i]] && !vis[i])
vis[fa[i]] = vis[i] = 1, res.push_back(i);
sort(res.begin(), res.end());
printf("%lld
", 1000 * (ll)res.size());
for (int i = 0; i < res.size() - 1; i++) {
printf("%d ", res[i]);
}
printf("%d", res.back());
}