傳送門
思路：
我們需要抓住唯一的重要資訊點"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 <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <string> #include <map> #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 <= n; ++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 <= n; ++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 <= n; ++i) { printf("%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 */
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/228744.html
標籤：其他
上一篇：C++實作任意進制的相互轉換