---
# System prepended metadata

title: KOI 23 Ant Colony
tags: [statement]

---

https://www.acmicpc.net/problem/28328

# KOI 23 Ant Colony

In KOI Park, there is an anthill where multiple ants gather. The anthill consists of $N$ rooms, and there are $N - 1$ corridors directly connecting different anthills, allowing ants to move between any two different anthills through these corridors. In other words, the anthill can be represented as a tree with $N$ vertices, where each room is numbered from $1$ to $N$.

Each room can host at most one ant. For each corridor of the current anthill, only one of the two connected rooms can have an ant living in it. Let $K$ be the maximum number of ants living on the anthill, currently there are $K$ ants.

Consider adding a new corridor between rooms $i$ and $j$, $1 \le i < j \le N$. For how many pairs of $(i,j)$, is it still possible to accomodate all $K$ ants? 

# Input

The first line contains an integer $N$.

The next $N-1$ lines contain two integers each, $u,v$ stating there's a corridor between $u$ and $v$

# Output

Print the number of pairs of $(i,j)$, such that it is possible to accomodate all $K$ ants.

# Constraints

![image](https://hackmd.io/_uploads/BkWf7QzKT.png)


# Subtasks

![image](https://hackmd.io/_uploads/BkjzQmMtT.png)


# Samples 

See the original statement for samples to copy

Sample 1 - $K=3$. The only good pairs are $(1,2)$, $(1,3)$, $(1,4)$


