裏紙

ほぼ競プロ、たまに日記

CS Academy #38 - Tree Antichain (Hard)

問題

CS Academy

問題概要

頂点数nの木が与えられる。長さnの順列aを考え、それを頂点に対応させる時、a_ia_{i+1} (1 \le i \le n-1)の間にいずれも辺がないような順列の中で辞書順最小のものを求めよ。

  • テストケース数T : 1 \le T \le 10^4
  •  2 \le n \le 10^5
  • テストケース全体でのnの和は10^5を超えない

イデア

同じラウンドに(Easy)というのも存在していたが、そちらは辞書順最小という条件がはずれたもの。このときはグラフがスターでなければ構成可能。適当に根を決めて根からの距離の偶奇で二部グラフになるので、偶数側を並べて奇数側をならべればよい(変わり目だけは辺がないように気をつける)。

この中でも辞書順最小のものが知りたい、と言う話になってくる。グラフがスターだと構成できないという話があったが、これをもう少し広げると、ある順列a_1 , a_2 , \ldots , a_nという順列を考えたときに、前から順番にa_1の頂点から順に削除をしていくという操作を考えると、この操作の過程で、一度もグラフがスターになることがなければこの順列はvalidなものであるということが言える。以下でこれを確認する:

まず、木を二部グラフと見なす(適当な根からの頂点の偶奇とかで簡単に色分けできる)。黒と白に色分けすることにしよう。

上で書いていたことを少し言い換えて、今、a_1 , a_2, \ldots , a_kという順列があるような状況を考える。このk個の頂点を取り除いたグラフがスターになっていなければその順列はそれ以降、n番目まで妥当なものを構築できることを示す。

今、a_kの頂点は白、つまり a_kと接続している頂点は全部黒であるとする。残っているグラフが非連結ならば、a_k以降は白い頂点を全部並べて、その後に黒い頂点を並べればそれは問題なく構築できる。もし、残っているグラフが連結ならば(スターではない)、白い頂点を全部並べて、その後に黒い頂点を並べるのだが、白から黒への切り替わるタイミングで辺があるような2頂点を選ばないように気をつければ良い(そしてスターでなければこのようなペアは必ずある)(証明終)。

この事実が正しいということがわかると、このn個の順列は前から順番に決定していくことができるようになる。

i番目の頂点をどれにするかを決める段階を考えると、まだ使われていない頂点をsetで管理しながら、頂点番号が小さい順に追加してよいかをチェックしていく。チェックすべきことは、a_{i-1}と接続していないこと、もしその頂点を選んだ後に残るグラフがスターになっていないこと(これは、残っている頂点の次数をmultisetで管理することでチェックできる)の2つになる。

これをチェックしながら貪欲にやっていくことで構築できる。コードを書いてみるとO(n^2)になっているように見えるがそうではない。失敗するパターンとしては、隣接してるときとスターになってしまう時がありえるが、まず隣接していて失敗するというのは全部を構築する過程でO(n)回しか起こらない。またスターになって失敗する状況というのは、グラフから1点を取り除くとスターになるようなグラフについて、そのような取り除くと残るグラフがスターになるような頂点はi番目のステップにおいてたかだか2点しかないということを考えると、setなどの操作を考慮して全体でO(n \log n)で処理ができる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

void solve()
{
    int n;
    scanf(" %d", &n);

    vector<set<int>> G(n);

    rep(i,n-1)
    {
        int x,y;
        scanf(" %d %d", &x, &y);
        --x;
        --y;
        G[x].insert(y);
        G[y].insert(x);
    }

    multiset<int> deg;
    set<int> rem;
    rep(i,n)
    {
        deg.insert(G[i].size());
        rem.insert(i);
    }

    // この時点でスターの場合、不可能
    if(*deg.rbegin() == n-1)
    {
        printf("-1\n");
        return;
    }

    vector<int> ans;
    rep(i,n-1)
    {
        for(int nx:rem)
        {
            // 直前の頂点と接続していたらダメ
            if(i>0 && G[ans[i-1]].count(nx)) continue;
            // 実際に削除
            for(int j:G[nx])
            {
                deg.erase(deg.find(G[j].size()));
                G[j].erase(nx);
                deg.insert(G[j].size());
            }
            deg.erase(deg.find(G[nx].size()));

            // OK
            if(*deg.rbegin()<n-2-i || i==n-2)
            {
                ans.pb(nx);
                rem.erase(nx);
                break;
            }

            // スターになってしまったのでダメ
            for(int j:G[nx])
            {
                deg.erase(deg.find(G[j].size()));
                G[j].insert(nx);
                deg.insert(G[j].size());
            }
            deg.insert(G[nx].size());
        }
    }

    for(int x:ans) printf("%d ", x+1);
    printf("%d\n", *rem.begin()+1);
}

int main()
{
    int T;
    scanf(" %d", &T);
    while(T--) solve();
    return 0;
}