#include #define rep(i,a,n) for(int i = a; i < n; i++) #define yes (cout << "Yes" << endl) #define YES (cout << "YES" << endl) #define no (cout << "No" << endl) #define NO (cout << "NO" << endl) #define pb push_back #define pf push_front #define mp make_pair #define fi first #define se second #define all(a) (a).begin(),(a).end() using namespace std; using ll = long long; using ull = unsigned long long; using vi = vector; using vd = vector; using vl = vector; using vs = vector; using vvi = vector>; using Graph = vector>; const int mod = 998244353; const int MOD = 1000000007; const double pi = 3.141592653589793238; const string abc = "abcdefghijklmnopqrstuvwxyz"; int dight_sum(int t) { int ans = 0; while(t >= 10) { ans += t % 10; t /= 10; } ans += t; return ans; } vector seen; void dfs(const Graph &G, int v) { seen[v] = true; // v を訪問済にする // v から行ける各頂点 next_v について for (auto next_v : G[v]) { if (seen[next_v]) continue; // next_v が探索済だったらスルー dfs(G, next_v); // 再帰的に探索 } } ll gcd(ll a,ll b){ while(b!=0){ a%=b; swap(a,b); } return a; } struct unionfind { vector par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2 unionfind (int N) : par(N) { //最初は全てが根であるとして初期化 for(int i = 0; i < N; i++) par[i] = i; } int root(int x) { // データxが属する木の根を再帰で得る:root(x) = {xの木の根} if (par[x] == x) return x; return par[x] = root(par[x]); } void unite(int x, int y) { // xとyの木を併合 int rx = root(x); //xの根をrx int ry = root(y); //yの根をry if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時:xの根rxをyの根ryにつける } bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す int rx = root(x); int ry = root(y); return rx == ry; } }; long long factorial(long long k) { ll ans = 1; rep(i,1,k + 1) { ans *= i; } return ans; } int main () { cout << fixed << setprecision(10); int n; cin >> n; int m = n -1; Graph G(n); rep(i,0,m) { int a,b; cin >> a >> b; a--; b--; G[a].pb(b); G[b].pb(a); } rep(i,0,n) { vector dist(n, -1); // 全頂点を「未訪問」に初期化 queue que; // 初期条件 (頂点 0 を初期ノードとする) dist[i] = 0; que.push(i); // 0 を橙色頂点にする // BFS 開始 (キューが空になるまで探索を行う) while (!que.empty()) { int v = que.front(); // キューから先頭頂点を取り出す que.pop(); // v から辿れる頂点をすべて調べる for (int nv : G[v]) { if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない // 新たな白色頂点 nv について距離情報を更新してキューに追加する dist[nv] = dist[v] + 1; que.push(nv); } } int cnt = 0; rep(i,0,n) { if(dist[i] == 2) cnt++; } cout << cnt << endl; } }