排序 但是 cnblogs const 每次 sof pac max
题目大意:给你一棵树,起初所有点都是白色的,你每次都能选择一个白点 i,将这个点 i 到根路径上的所有到 i 的距离
n<=100000
题解:显然贪心啊,但是我一开始居然写了树剖。。。
因为叶子节点是一定要染的,所以我们可以将所有点按 DFS 序排序,从后往前染。记录 vis[i],表示之前已经将所有到 i 的距离 <=vis[i] 的点染成了黑色;再维护 mx[i],表示之前染过的点最多能将到 i 的距离 <=mx[i] 的点染成黑色。然后用当前的 vis 和 mx 去更新 fa 就行了。
- #include < cstdio > #include < cstring > #include < iostream > using namespace std;
- const int maxn = 100010;
- int n,
- cnt,
- ans;
- int fa[maxn],
- tag[maxn],
- k[maxn],
- p[maxn],
- head[maxn],
- nxt[maxn],
- to[maxn],
- ml[maxn];
- void add(int a, int b) {
- to[cnt] = b,
- nxt[cnt] = head[a],
- head[a] = cnt++;
- }
- void dfs(int x) {
- p[++p[0]] = x;
- for (int i = head[x]; i != -1; i = nxt[i]) dfs(to[i]);
- }
- int main() {
- scanf("%d", &n);
- int i,
- a;
- memset(head, -1, sizeof(head));
- for (i = 2; i <= n; i++) scanf("%d", &fa[i]),
- add(fa[i], i);
- for (i = 1; i <= n; i++) scanf("%d", &k[i]);
- dfs(1);
- for (i = n; i >= 1; i--) {
- a = p[i];
- ml[a] = max(ml[a], k[a]);
- if (!tag[a]) tag[a] = ml[a],
- ans++;
- ml[fa[a]] = max(ml[fa[a]], ml[a] - 1),
- tag[fa[a]] = max(tag[fa[a]], tag[a] - 1);
- }
- printf("%d", ans);
- return 0;
- }
【CodeM 初赛 B 轮】A 贪心
来源: http://www.bubuko.com/infodetail-2137744.html