結果
| 問題 | No.3405 Engineering University of Tree |
| コンテスト | |
| ユーザー |
 Nachia
|
| 提出日時 | 2025-11-28 04:53:37 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 385 ms / 2,000 ms |
| コード長 | 24,125 bytes |
| 記録 | |
| コンパイル時間 | 1,295 ms |
| コンパイル使用メモリ | 118,260 KB |
| 実行使用メモリ | 37,904 KB |
| 最終ジャッジ日時 | 2025-12-11 23:30:18 |
| 合計ジャッジ時間 | 9,013 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 21 |
ソースコード
/*
https://gemini.google.com/app
思考モード（3 Pro 搭載）
=================================================v プロンプト v============================
以下は、競技プログラミング形式の自作問題です。解法を提案してください。
* 実行時間 : 2 sec
* メモリ : 1024 MB
## 問題文
国立こゃーそ大学では今年も学祭の準備が進められています。
こゃーそ大学のキャンパスには $N$ 個の**広場**と $N-1$ 個の**道路**があります。
各道路はちょうど $2$ つの広場をつないでいます。 $N-1$ 個の道路によって、すべての広場は互いに行き来できるようになっています。
広場には $1$ から $N$ の番号が、道路には $1$ から $N-1$ の番号がついています。
広場 $k$ には $C_k$ 個の道路が接続されていて、それらの番号は $E_{k,1},E_{k,2},\ldots ,E_{k,C_k}$ です。
これから、キャンパスの地図上になるべく多くの**歯車のシンボル**を描こうとしています。
レベル $K$ の**歯車のシンボル**は、中心となる広場 $1$ つと、それに接続している道路 $K$ 個を選ぶことで描くことができます。
地図上にいくつかの歯車のシンボルを書くときは、それらが互いに重ならないようにします。
つまり、同じ広場を中心とするシンボルを $2$ つ以上描いたり、シンボルを書く工程全体で同じ道路を $2$ 回以上選んだりしてはいけません。
また、地図上に描く歯車のシンボルはすべて同じレベルにすることが決まっています。
そこで、 $k=1,2,\ldots ,N-1$ のそれぞれについて、レベル $k$ の歯車のシンボルを描くことができる最大の個数を求めてください。
## 制約
入力は以下の制約を満たします。
* $2\leq N \leq 200\, 000$
* $1 \leq E_{i,j} \leq N-1$
* $E_{i,j} \neq E_{i,k}$ $(1 \leq i \leq N , 1 \leq j \lt k \leq C_i)$ すなわち、 $1$ つの広場に同じ道路が $2$ 回以上つながっていることはない。
* $E_{i,j}$ $(1 \leq i \leq N, 1 \leq j \leq C_i)$ の値として、 $1,2,\ldots ,N-1$ がちょうど $2$ 回ずつ現れる。
* すべての広場は互いに行き来できる。
* 入力される値はすべて整数
## 入力
```
$N$
$C_1$ $E_{1,1}$ $E_{1,2}$ $\cdots$ $E_{1,C_1}$
$C_2$ $E_{2,1}$ $E_{2,2}$ $\cdots$ $E_{2,C_2}$
$\vdots$
$C_N$ $E_{N,1}$ $E_{N,2}$ $\cdots$ $E_{N,C_N}$
```
## 出力
$k=1,2,\ldots ,N-1$ についての答えをこの順に、空白区切りで出力してください。
## 入出力例
入力例 1
```
3
1 1
2 2 1
1 2
```
出力例 1
```
2 1
```
入力例 2
```
15
1 5
1 2
1 7
1 10
2 3 13
1 6
3 9 14 1
1 8
1 11
2 12 4
3 11 9 5
4 12 10 1 6
3 14 2 7
2 4 13
2 3 8
```
出力例 2
```
14 6 3 1 0 0 0 0 0 0 0 0 0 0
```
======================================^ プロンプト ^===v 出力 v============================
この自作問題は、\*\*木の性質と貪欲法、そして計算量のならし解析（Amortized Analysis）\*\*を組み合わせた、非常に教育的で良質な問題ですね。制約 $N \le 200,000$ と実行時間 2秒に対し、$O(N^2)$ の解法は間に合わないため、全体で $O(N)$ または $O(N \log N)$ 程度の効率的な解法が求められます。
以下に、解法の提案（解説）と解答コード（C++）を作成しました。
-----
### 解法のアプローチ
この問題は、各 $K$ について独立に最大独立集合のようなものを求める問題に見えますが、単純な貪欲法が適用できる構造をしています。
#### 1\. 固定された $K$ に対する貪欲法
ある $K$ が固定されているとき、以下の貪欲法で「歯車のシンボル」の最大個数を求めることができます。
* **葉から根へ（ボトムアップ）**：
木の適当な頂点（例えば頂点1）を根とし、葉から順に処理を行います（帰がけ順の探索）。
* **判定ロジック**：
頂点 $u$ について考えます。$u$ に接続している辺のうち、「すでに子孫側の歯車で使用されてしまった辺」を除いた残りの本数を $R_u$ とします。
* もし $R_u \ge K$ ならば、$u$ を中心とする歯車を作成します。このとき、$u$ は親との間の辺を使用する必要はありません（子側の辺だけで足りるため）。
* もし $R_u = K-1$ ならば、$u$ を中心とする歯車を作成します。ただし、不足分を補うために**親との間の辺を使用**します（親側はこの辺を使えなくなります）。
* もし $R_u < K-1$ ならば、$u$ で歯車を作ることはできません。親との間の辺は未使用のまま残ります。
この貪欲法は、「子孫側で完結できるなら完結させ、あと1本足りないときだけ親の助けを借りる」という戦略であり、木上のマッチング問題などで最適解を与える一般的な手法です。この処理は $O(N)$ で行えます。
#### 2\. 全ての $K$ に対する高速化 ($O(N^2) \to O(N)$)
$K$ を $1$ から $N-1$ まで変化させて毎回 $O(N)$ かけると全体で $O(N^2)$ となり、TLE（時間切れ）します。しかし、以下の事実に着目すると高速化できます。
1. **次数の制約**：次数が $K$ 未満の頂点は、絶対に歯車の中心にはなれません。
2. **静的な辺と動的な辺**：
* 次数が $K$ 未満の頂点は「ただ辺を提供するだけの存在（葉のような扱い）」になります。
* 次数が $K$ 以上の頂点同士がつながっている部分だけが、探索すべき「有効な森（forest）」を構成します。
$K$ が増えるにつれて、「有効な頂点」は減っていきます。
全 $K$ にわたって処理される頂点数の総和は $\sum_{v} \text{deg}(v) = 2(N-1)$ です。
したがって、\*\*「次数が $K$ 以上の頂点だけで構成される森」\*\*を動的に管理し、その森の上だけで貪欲法を行えば、全体計算量を $O(N)$ （ソートを含めると $O(N \log N)$）に抑えることができます。
#### 3\. 実装のポイント
* **隣接リストのソート**：各頂点の隣接リストを「隣接頂点の次数」の昇順にソートしておきます。こうすることで、次数 $K$ 未満になった隣接頂点（＝静的な辺供給源）を効率的にスキップできます。
* **ポインタの管理**：各頂点 $u$ について「現在有効な隣接頂点の開始位置」を保持するポインタ `ptr[u]` を持ち、$K$ が増えるごとに進めていきます。
* **探索**：各 $K$ において、「有効な頂点集合」に対してDFSを行い、ボトムアップに貪欲法を適用します。
### 解答コード (C++)
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
// 高速化のための入出力設定
void fast_io() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
int main() {
fast_io();
int N;
if (!(cin >> N)) return 0;
// 入力は「各頂点につながる辺のID」形式。
// まず辺IDごとに端点を集計して、通常の隣接リストに変換する。
// エッジ数はN-1、IDは1～N-1。
vector<vector<int>> edge_to_nodes(N);
// 入力受け取りとグラフ構築
// 各頂点について
for (int i = 0; i < N; ++i) {
int C;
cin >> C;
for (int j = 0; j < C; ++j) {
int eid;
cin >> eid;
--eid; // 0-based indexに変換
edge_to_nodes[eid].push_back(i);
}
}
// 隣接リスト構築
vector<vector<int>> adj(N);
vector<int> deg(N, 0);
for (int i = 0; i < N - 1; ++i) {
int u = edge_to_nodes[i][0];
int v = edge_to_nodes[i][1];
adj[u].push_back(v);
adj[v].push_back(u);
}
// 次数を計算
for (int i = 0; i < N; ++i) {
deg[i] = adj[i].size();
}
// 隣接リストを「隣接頂点の次数」の昇順にソート
// これにより、Kが増えたときに「無効になった隣接頂点」がリストの先頭に集まる
for (int i = 0; i < N; ++i) {
sort(adj[i].begin(), adj[i].end(), [&](int a, int b) {
return deg[a] < deg[b];
});
}
// 次数ごとに頂点をバケット分けする
vector<vector<int>> nodes_by_deg(N);
for (int i = 0; i < N; ++i) {
nodes_by_deg[deg[i]].push_back(i);
}
// 現在「有効」な頂点の集合（最初は全頂点）
// リストの削除を効率化するため、swap削除ができるvectorで管理し、
// 各頂点がvectorのどこにいるかをpos配列で管理する。
vector<int> active_nodes(N);
iota(active_nodes.begin(), active_nodes.end(), 0);
vector<int> pos_in_active(N);
iota(pos_in_active.begin(), pos_in_active.end(), 0);
// 各頂点の隣接リストのどこまでが「次数 < K」な無効頂点かを示すポインタ
vector<int> ptr(N, 0);
// 訪問管理用 (Kごとにvisitedをリセットする代わりにトークンを使う)
vector<int> visited(N, -1);
// DFS用のスタック (再帰呼び出しを避けるため)
vector<int> stack;
stack.reserve(N);
vector<int> traversal_order;
traversal_order.reserve(N);
vector<int> parent(N, -1);
// K = 1 から N-1 まで計算
for (int K = 1; K < N; ++K) {
// 1. 次数が K-1 の頂点を active_nodes から削除する
// (これらは次数不足のため、もはや歯車の中心にはなり得ない)
for (int u : nodes_by_deg[K - 1]) {
int current_pos = pos_in_active[u];
int last_node = active_nodes.back();
// swapしてpop back
active_nodes[current_pos] = last_node;
pos_in_active[last_node] = current_pos;
active_nodes.pop_back();
// uはもうactiveではないのでposは無効化（必要なら）
}
int answer = 0;
// 2. 有効な頂点集合に対して森の探索を行う
// 森の各成分ごとにDFSを行い、帰がけ順(post-order)を取得する
traversal_order.clear();
for (int root : active_nodes) {
if (visited[root] == K) continue;
// 新しい連結成分の探索開始
stack.clear();
stack.push_back(root);
visited[root] = K;
parent[root] = -1;
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
traversal_order.push_back(u);
// 隣接リストを見て、有効な隣接点（deg >= K）をスタックに積む
// ptr[u] を進めて、無効な隣接点（deg < K）をスキップする
while (ptr[u] < (int)adj[u].size() && deg[adj[u][ptr[u]]] < K) {
ptr[u]++;
}
// 有効な隣接点のみ走査
for (int i = ptr[u]; i < (int)adj[u].size(); ++i) {
int v = adj[u][i];
if (visited[v] != K) {
visited[v] = K;
parent[v] = u; // 探索木上の親を記録
stack.push_back(v);
}
}
}
}
// 3. 帰がけ順（traversal_orderの逆順）で貪欲法を適用
// needs_parent[u] : uが歯車になるために親との辺を必要とするか
// この配列はKごとに初期化が必要だが、traversal_orderに含まれる頂点のみリセットすればO(N)にならない
// （ここではmapや毎回vector生成を避けるため、使いまわす配列を用意する）
// ただし、単純なbool値で十分。
// 一時的な状態保持配列（このループ内でのみ有効）
// is_consumed[u] : uと親の間の辺が、uによって消費されたか
// ただし配列全体をリセットすると遅いので、必要な部分だけ使うか、
// あるいはDFSの戻り値のように処理する。
// ここでは配列 used_parent_edge[u] を使う。初期化は不要（上書きされるため）。
// ただし葉の判定のために注意が必要。
static vector<bool> used_parent_edge(N);
// traversal_order は 行きがけ順(pre-order)に近い順（スタック実装による）なので
// 逆順に回すと帰がけ順(post-order)になる。
for (int i = (int)traversal_order.size() - 1; i >= 0; --i) {
int u = traversal_order[i];
// uで使用可能な辺の数を数える
// 1. 静的な辺（次数 < K の隣接点からの辺）
// これは ptr[u] の値そのものである（隣接リストは次数昇順ソート済みのため）
int available = ptr[u];
// 2. 動的な辺（次数 >= K の子供からの辺）
// 有効な隣接点 v (parent[u]を除く) について、
// vが親(u)との辺を使っていなければ、uが使える。
// 再度隣接リストを走査して子供を確認
// (このループは全K合計で O(N) 回しか回らないので高速)
for (int j = ptr[u]; j < (int)adj[u].size(); ++j) {
int v = adj[u][j];
if (v == parent[u]) continue; // 親はスキップ
// v が親(u)との辺を使っていないなら、uが使える
if (!used_parent_edge[v]) {
available++;
}
}
// 判定
if (available >= K) {
// 親の辺を使わずに達成
answer++;
used_parent_edge[u] = false;
} else if (available == K - 1) {
// 親の辺を使って達成（uが根でない場合のみ）
if (parent[u] != -1) {
answer++;
used_parent_edge[u] = true;
} else {
used_parent_edge[u] = false;
}
} else {
// 達成不可
used_parent_edge[u] = false;
}
}
cout << answer << (K == N - 1 ? "" : " ");
}
cout << endl;
return 0;
}
```
### 複雑性解析（Complexity Analysis）
* **前処理**:
* グラフ構築: $O(N)$
* 隣接リストのソート: $\sum_{u} \deg(u) \log(\deg(u))$。最大で $O(N \log N)$。
* **メインループ**:
* ループは $K=1 \dots N-1$ まで回ります。
* 各反復において、「有効な頂点（次数 $\ge K$）」とその間の「有効な辺」のみが参照されます。
* ある辺 $(u, v)$ が参照される回数は、$\min(\deg(u), \deg(v))$ 回以下です。なぜなら、どちらかの次数が $K$ を下回ると、その辺は「静的な辺（`ptr` でスキップされる領域）」へ移動し、個別の走査対象から外れるからです。
* 木において $\sum_{(u,v) \in E} \min(\deg(u), \deg(v))$ は $O(N)$ になることが知られています（スターグラフやパスグラフで確認できます）。
* したがって、DFSおよび貪欲法判定の総ステップ数は $O(N)$ です。
* **全体計算量**: $O(N \log N)$
* **空間計算量**: $O(N)$
この解法であれば、実行時間制限 2.0 sec に対して十分高速に動作します。
=======================================================^ 出力 ^============================
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
// 高速化のための入出力設定
void fast_io() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
int main() {
fast_io();
int N;
if (!(cin >> N)) return 0;
// 入力は「各頂点につながる辺のID」形式。
// まず辺IDごとに端点を集計して、通常の隣接リストに変換する。
// エッジ数はN-1、IDは1～N-1。
vector<vector<int>> edge_to_nodes(N);
// 入力受け取りとグラフ構築
// 各頂点について
for (int i = 0; i < N; ++i) {
int C;
cin >> C;
for (int j = 0; j < C; ++j) {
int eid;
cin >> eid;
--eid; // 0-based indexに変換
edge_to_nodes[eid].push_back(i);
}
}
// 隣接リスト構築
vector<vector<int>> adj(N);
vector<int> deg(N, 0);
for (int i = 0; i < N - 1; ++i) {
int u = edge_to_nodes[i][0];
int v = edge_to_nodes[i][1];
adj[u].push_back(v);
adj[v].push_back(u);
}
// 次数を計算
for (int i = 0; i < N; ++i) {
deg[i] = adj[i].size();
}
// 隣接リストを「隣接頂点の次数」の昇順にソート
// これにより、Kが増えたときに「無効になった隣接頂点」がリストの先頭に集まる
for (int i = 0; i < N; ++i) {
sort(adj[i].begin(), adj[i].end(), [&](int a, int b) {
return deg[a] < deg[b];
});
}
// 次数ごとに頂点をバケット分けする
vector<vector<int>> nodes_by_deg(N);
for (int i = 0; i < N; ++i) {
nodes_by_deg[deg[i]].push_back(i);
}
// 現在「有効」な頂点の集合（最初は全頂点）
// リストの削除を効率化するため、swap削除ができるvectorで管理し、
// 各頂点がvectorのどこにいるかをpos配列で管理する。
vector<int> active_nodes(N);
iota(active_nodes.begin(), active_nodes.end(), 0);
vector<int> pos_in_active(N);
iota(pos_in_active.begin(), pos_in_active.end(), 0);
// 各頂点の隣接リストのどこまでが「次数 < K」な無効頂点かを示すポインタ
vector<int> ptr(N, 0);
// 訪問管理用 (Kごとにvisitedをリセットする代わりにトークンを使う)
vector<int> visited(N, -1);
// DFS用のスタック (再帰呼び出しを避けるため)
vector<int> stack;
stack.reserve(N);
vector<int> traversal_order;
traversal_order.reserve(N);
vector<int> parent(N, -1);
// K = 1 から N-1 まで計算
for (int K = 1; K < N; ++K) {
// 1. 次数が K-1 の頂点を active_nodes から削除する
// (これらは次数不足のため、もはや歯車の中心にはなり得ない)
for (int u : nodes_by_deg[K - 1]) {
int current_pos = pos_in_active[u];
int last_node = active_nodes.back();
// swapしてpop back
active_nodes[current_pos] = last_node;
pos_in_active[last_node] = current_pos;
active_nodes.pop_back();
// uはもうactiveではないのでposは無効化（必要なら）
}
int answer = 0;
// 2. 有効な頂点集合に対して森の探索を行う
// 森の各成分ごとにDFSを行い、帰がけ順(post-order)を取得する
traversal_order.clear();
for (int root : active_nodes) {
if (visited[root] == K) continue;
// 新しい連結成分の探索開始
stack.clear();
stack.push_back(root);
visited[root] = K;
parent[root] = -1;
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
traversal_order.push_back(u);
// 隣接リストを見て、有効な隣接点（deg >= K）をスタックに積む
// ptr[u] を進めて、無効な隣接点（deg < K）をスキップする
while (ptr[u] < (int)adj[u].size() && deg[adj[u][ptr[u]]] < K) {
ptr[u]++;
}
// 有効な隣接点のみ走査
for (int i = ptr[u]; i < (int)adj[u].size(); ++i) {
int v = adj[u][i];
if (visited[v] != K) {
visited[v] = K;
parent[v] = u; // 探索木上の親を記録
stack.push_back(v);
}
}
}
}
// 3. 帰がけ順（traversal_orderの逆順）で貪欲法を適用
// needs_parent[u] : uが歯車になるために親との辺を必要とするか
// この配列はKごとに初期化が必要だが、traversal_orderに含まれる頂点のみリセットすればO(N)にならない
// （ここではmapや毎回vector生成を避けるため、使いまわす配列を用意する）
// ただし、単純なbool値で十分。
// 一時的な状態保持配列（このループ内でのみ有効）
// is_consumed[u] : uと親の間の辺が、uによって消費されたか
// ただし配列全体をリセットすると遅いので、必要な部分だけ使うか、
// あるいはDFSの戻り値のように処理する。
// ここでは配列 used_parent_edge[u] を使う。初期化は不要（上書きされるため）。
// ただし葉の判定のために注意が必要。
static vector<bool> used_parent_edge(N);
// traversal_order は 行きがけ順(pre-order)に近い順（スタック実装による）なので
// 逆順に回すと帰がけ順(post-order)になる。
for (int i = (int)traversal_order.size() - 1; i >= 0; --i) {
int u = traversal_order[i];
// uで使用可能な辺の数を数える
// 1. 静的な辺（次数 < K の隣接点からの辺）
// これは ptr[u] の値そのものである（隣接リストは次数昇順ソート済みのため）
int available = ptr[u];
// 2. 動的な辺（次数 >= K の子供からの辺）
// 有効な隣接点 v (parent[u]を除く) について、
// vが親(u)との辺を使っていなければ、uが使える。
// 再度隣接リストを走査して子供を確認
// (このループは全K合計で O(N) 回しか回らないので高速)
for (int j = ptr[u]; j < (int)adj[u].size(); ++j) {
int v = adj[u][j];
if (v == parent[u]) continue; // 親はスキップ
// v が親(u)との辺を使っていないなら、uが使える
if (!used_parent_edge[v]) {
available++;
}
}
// 判定
if (available >= K) {
// 親の辺を使わずに達成
answer++;
used_parent_edge[u] = false;
} else if (available == K - 1) {
// 親の辺を使って達成（uが根でない場合のみ）
if (parent[u] != -1) {
answer++;
used_parent_edge[u] = true;
} else {
used_parent_edge[u] = false;
}
} else {
// 達成不可
used_parent_edge[u] = false;
}
}
cout << answer << (K == N - 1 ? "" : " ");
}
cout << endl;
return 0;
}