#include using namespace std; // AtCoder Beginner Contest 067 (D - Fennec VS. Snuke) を 参照. // José Marcos氏. // https://abc067.contest.atcoder.jp/submissions/1424740 // -> 一部改変して, 動作確認した. // 頂点start と 頂点end との 距離 に関する情報を取得(幅優先探索 Breadth First Search). int bfs(int start, int end, int size, vector G[]) { // 1. 各頂点 と 頂点start との 距離 に関する情報を保存. vector dist(size + 1, 0); // 2. queue の 設定. queue Q; Q.push(start); dist[start] = 0; // 3. queue が 空になるまで, 探索. while(!Q.empty()){ int u = Q.front(); Q.pop(); // cout << u << " " << dist[u] << endl; for(int v : G[u]){ if(dist[v] == 0){ dist[v] = dist[u] + 1; Q.push(v); } } } // 4. 頂点start と 頂点end との 距離 を 返却. return dist[end]; } int main() { // 1. 入力情報取得. int N; cin >> N; vector G[N + 1]; // 頂点の時数を保存. int d[N + 1]; for(int i = 0; i <= N; i++) d[i] = 0; for(int i = 1; i < N; i++){ int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); d[a]++, d[b]++; } // 2. 木を道に変換. // 2-1. 次数1 の 頂点は? vector d1; for(int i = 0; i <= N; i++) if(d[i] == 1) d1.push_back(i); // 2-2. 次数3以上 の 頂点は? vector d3; for(int i = 0; i <= N; i++) if(d[i] >= 3) d3.push_back(i); // 2-3. 各次数3以上 の 頂点と, 次数1 の頂点 の距離は? // -> 計算後, 次数3以上の頂点が, 次数2になるために, 必要な組み換え. int ans = 0; for(auto &p : d3){ vector v; for(auto &q : d1){ int dist = bfs(p, q, N, G); v.push_back(dist); cout << "p=" << p << " q=" << q << " dist=" << dist << endl; } // 距離の短い順にsort. sort(v.begin(), v.end()); // 距離を順次加算. for(int i = 0; i < d[p] - 2; i++) ans += v[i]; } // 3. 後処理. cout << ans << endl; return 0; }