BOJ 28252 - 리프 수열

BOJ 28252 - 리프 수열

우선 트리의 리프가 늘어날 수 없으므로 $a_i < a_{i+1}$ 라면 정답은 불가능하다.

또한 $a_N$이 $1 \ \text{or}\ 2$가 아니라면 불가능하다.

트리가 계속 줄어들면서 마지막엔 루트가 한개 혹은 두개만 남기 때문이다.

또한 $1$이 두 번 이상 등장한다면 불가능하다. leaf가 한개인 상태가 계속 지속될 수 없다.

구성하는 방법은 뒤에서부터 보면서 구성하는 것이다.

예제처럼 3 2 2 1 이라면 $1$을 루트노드로 해주고

이제 거기에 두개를 붙여주고,

두개를 또 각각 하나씩 붙여주고

세개는 부모들에게 하나씩 나눠주고 마지막 부모에게 남은것을 모두 붙이면 된다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);

   for (int i = 1; i < n; i++) {
      if (a[i] > a[i - 1]) {
         cout << -1;
         return;
      }
   }
   if (a[n - 1] > 2) {
      cout << -1;
      return;
   }
   for (int i = 0; i < n - 1; i++) {
      if (a[i] == 1) {
         cout << -1;
         return;
      }
   }

   vector<pi> edges;
   vi par;
   int nxt = 2;
   par.pb(1);
   if (a[n - 1] == 2) {
      par.pb(2);
      edges.pb({1, 2});
      nxt++;
   }
   for (int i = n - 2; i >= 0; i--) {
      int c = a[i];
      vi cur;
      for (int j: par) {
         edges.pb({j, nxt});
         cur.pb(nxt);
         nxt++;
      }
      int diff = a[i] - a[i + 1];
      while (diff--) {
         edges.pb({par.back(), nxt});
         cur.pb(nxt);
         nxt++;
      }
      par = cur;
   }
   cout << sz(edges) + 1 << endl;
   for (auto &[a, b]: edges) cout << a << ' ' << b << endl;
}