「CF1286B」Numbers on Tree

传送门

不难发现，如果有解的话，一定存在一组解使得 \(a_i\) 恰为 \(n\) 的一个排列。

否则，如果不存在这样一组解，就肯定是无解。

那么我们就尝试构造这样的解（从小到大赋值）。

如果我们设一个 \(d_i\)，表示 \(i\) 号节点的子树中还有 \(d_i\) 个节点要对它贡献。

那么我们肯定会把 \(d_i = 0\) 的节点第一时间拿出来赋值。

然后我们拿它对它的祖先们都贡献一次，如果祖先的 \(d_i\) 变为 \(0\)，那么也拿来贡献。

对于同时有很多个 \(d_i = 0\) 的情况，我们就优先更新深度较小的节点的值，因为我们不能再让深度大的点对深度小的点贡献，所以就要给深度小的点赋较小的值。

具体实现开个堆就好了。

参考代码：

#include <cstdio>
#include <queue>
using namespace std;

const int _ = 2e3 + 5;

int tot, head[_]; struct Edge { int v, nxt; } edge[_ << 1];
void Add_edge(int u, int v) { edge[++tot] = (Edge) { v, head[u] }, head[u] = tot; }

int n, fa[_], c[_], a[_], dep[_]; priority_queue < pair < int, int > > Q;

void dfs(int u) {
    dep[u] = dep[fa[u]] + 1;
    for (int i = head[u]; i; i = edge[i].nxt) dfs(edge[i].v);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("cpp.in", "r", stdin), freopen("cpp.out", "w", stdout);
#endif
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d %d", fa + i, c + i), Add_edge(fa[i], i);
    for (int i = 1; i <= n; ++i) if (!fa[i]) { dfs(i); break ; }
    for (int i = 1; i <= n; ++i) if (!c[i]) Q.push(make_pair(-dep[i], i));
    while (!Q.empty()) {
        int u = Q.top().second; Q.pop();
        a[u] = ++a[0];
        for (int x = fa[u]; x; x = fa[x])
            if (!--c[x]) Q.push(make_pair(-dep[x], x));
    }
    if (a[0] < n) puts("NO");
    else {
        puts("YES");
        for (int i = 1; i <= n; ++i) printf("%d%c", a[i], " \n"[i == n]);
    }
    return 0;
}

「CF1286B」Numbers on Tree

原文：https://www.cnblogs.com/zsbzsb/p/13125303.html