問題概要

$k$ 個の葉をもつスターグラフを、レベル $k$ のスターと呼ぶことにする。

高橋君は、はじめ何個かのスターからなるグラフを持っている。これらのスターの頂点数の総和は $N$ である。

高橋君は、これらの星の葉同士を辺で結ぶことを繰り返して、頂点数 $N$ の木を作った (サイクルは生まないようにした)。

この木が与えられるので、もとのスターグラフのレベルを順に出力せよ。

制約

$3 \le N \le 2 \times 10^{5}$

解法 1：算数パズルをやる

与えられた木は、下図のように、いくつかのスターに分かれている。

レベル $k$ のスターの頂点数は $k+1$ なので、レベル $k$ のスターの個数を $x_{k}$ とすると

$3x_{2} + 4x_{3} + 5x_{4} + \dots = N$

が成り立つ。

また、この木の各頂点の次数に着目すると、「次数が 3 以上の頂点となれるのは、もとのスターの中心のみである」ということがわかる。

よって、レベル $2, 3, 4, \dots$ のスターのうち、レベル $3, 4, \dots$ のスターの個数 $x_{3}, x_{4}, \dots$ は、与えられたグラフの次数が $3, 4, \dots$ の頂点数に一致するので、簡単に求められる。

最後に、レベル $2$ のスターの個数 $x_{2}$ を考える。ここで上の方程式を思い出す。

$3x_{2} + 4x_{3} + 5x_{4} + \dots = N$

これより、

$x_{2} = \displaystyle \frac{N - 4x_{3} - 5x_{4} - \dots}{3}$

と求められる。計算量は $O(N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> deg(N, 0);
    for (int i = 0; i < N-1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        deg[u]++, deg[v]++;
    }
 
    // 各次数をもつ頂点の個数を数える
    vector<int> res(N + 1, 0);
    for (int i = 0; i < N; ++i) res[deg[i]]++;
    int sum = 0;
    for (int i = 3; i <= N; ++i) sum += (i+1) * res[i];
    
    // 2-star の個数を逆算
    res[2] = (N - sum) / 3;
    
    // 出力
    for (int v = 2; v <= N; ++v) {
        if (res[v]) {
            for (int i = 0; i < res[v]; ++i) cout << v << " ";
        }
    }
    cout << endl;
}

解法 2：DFS

こちらの方がもともと想定されていた解法だったっぽい。改めて、与えられる木を眺めると

葉から距離が 1 のところに「中心」がある
隣接するスターグラフの「中心」同士は、距離が 3 だけ離れている

ということがわかる。

よって、葉を 1 つ選んで、それを根とするような探索をして、深さが $1, 4, 7, 10, \dots$ の位置にある頂点の次数を見ていけばよい。

計算量は $O(N)$ となる。

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

void dfs(const Graph &G, int v, int p, int depth, vector<int> &res) {
    if (depth % 3 == 1) ++res[G[v].size()];
    for (auto v2 : G[v]) {
        if (v2 == p) continue;
        dfs(G, v2, v, depth+1, res);
    }
}

int main() {
    int N;
    cin >> N;
    Graph G(N);
    for (int i = 0; i < N-1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    // 葉を 1 つ求める
    int root = 0;
    for (int v = 0; v < N; ++v) if (G[v].size() == 1) root = v;
    
    // DFS する
    vector<int> res(N, 0);
    dfs(G, root, -1, 0, res);
    
    // 出力
    for (int v = 2; v < N; ++v) {
        if (res[v]) {
            for (int i = 0; i < res[v]; ++i) cout << v << " ";
        }
    }
    cout << endl;
}