問題

問題概要

頂点数 $n$ の木が与えられる。長さ $n$ の順列 $a$ を考え、それを頂点に対応させる時、 $a_i$ と $a_{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;
}

裏紙

ほぼ競プロ、たまに日記

CS Academy #38 - Tree Antichain (Hard)

問題

問題概要

アイデア

実装(C++)