1. Johngo学长首页
  2. 技术点详细复盘专题
  3. 数据结构和算法

D. Numbers on Tree（构造）【CF 1287】

• 数据结构和算法 • 阅读 99

传送门

D. Numbers on Tree（构造）【CF 1287】

思路：

我们需要抓住唯一的重要信息点”ci”，我的做法也是在猜想和尝试中得出的，之后再验证算法的正确性。

我们在构造中发现，如果树上出现了相同的数字，则会让树的构造变得不清晰。

我们尝试用不同的数值a[1]~a[n]去构造树，我们唯一知道的信息就是”ci”，如果a[1]~a[n] = 1~n（从小到大排序），则我们容易确定root的数值id[root] = a[c[root] + 1]。为什么？因为我们有1~n这n个数字，如果我们id[root] = a[c[root] + 1]，则root下面的点，无论怎么放置这n-1个数字都满足c[root]。如果该root的左边第一个son节点的c[x] = t，则id[x]为第c[x] + 1个数字（因为id[root]被使用了）好像也行的通（红字带入也行得通），然后我按着从左开始的dfs序模拟，发现问题就解决了，这样的方法是行的通的。为什么？模拟了之后才发现，因为我们选的是不同的数字，我们如果按着从左的dfs序一个个的解决子树，只要有足够的不同数字，则该方法一定是可以构造出当前子树的信息（带入红字理解），即子树之间独立不影响。用这个构造方法之前只需要先判断下所有的ci是不是合法，即该点下面如果只有x个数字，c[now]>x就是不合法的。代码下面有个样例，模拟下就理解了。

#include 
#include 
#include 
#include 
#include 
#include <string>
#include 
#include <set>

using namespace std;

const int N = 2e3 + 10;
vector<int > E[N];
set<int > hav;
int son[N], id[N];
int error;

int fun (int now, int pre)
{
    int sn = 0;
    for(auto to : E[now]) {
        if(to == pre) continue;
        sn += fun(to, now);
    }

    if(son[now] - 1 > sn) error = 1; ///判断ci是不是合法
    return sn + 1;
}

void dfs (int now, int pre)
{
    if(son[now] > hav.size()) { error = 1; return; }
    else {
        int tot = 0;
        for(auto& x: hav) {
            ++tot;
            if(tot == son[now]) {
                id[now] = x;
               // cout << x << endl;
                hav.erase(x);
                break;
            }
        }
    }

    for(auto to : E[now]) {
        if(to == pre) continue;
        dfs(to, now);
        if(error) return;
    }
}

void solve()
{
    int n, root;
    scanf("%d", &n);
    for(int i = 1; i i) {
        int x, cnt;
        scanf("%d%d", &x, &cnt);
        if(x != 0) {
            E[i].push_back(x);
            E[x].push_back(i);
        } else root = i;
        son[i] = cnt + 1;///第几个数字
    }

    for(int i = 1; i i) { hav.insert(i); }

    error = 0;
    fun(root, 0);
    if(error) {
        printf("NO\n");
        return;
    }
    dfs(root, 0);
    if(error) { printf("NO\n"); }
    else {
        printf("YES\n");
        for(int i = 1; i "%d ", id[i]); }
        printf("\n");
    }
}

int main()
{

    solve();

    return 0;
}
/*
13
0 5
1 2
2 0
2 1
4 0
4 1
6 0
6 0
1 1
9 0
9 2
11 0
11 0

*/

Original: https://www.cnblogs.com/SSummerZzz/p/14070624.html
Author: SummerMingQAQ
Title: D. Numbers on Tree（构造）【CF 1287】

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584291/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球