P4333 [JSOI2010] Game

Little L, Little H, and Little X from the JSOI training team, after intense training, always like to play a game called “number picking” to relax. This is a single-player game. You only need a blank sheet of paper and a pen. The player randomly writes a line of $n$ integers on the paper to form a sequence, and then the game starts. Each time, the player chooses one number from the left end or the right end of the original sequence, crosses it out from the original sequence, and writes it on the next line. After all numbers in the original sequence are crossed out, a new sequence of length $n$ appears on the second line, denoted as $S$. The score $P$ of sequence $S$ is computed as follows: $$P=S_1\times 5^0+S_2\times 5^1+\cdots+S_n\times 5^{n-1}$$ After computing the score $P$, convert it to binary. If the last three bits are $011$, the player wins the game; otherwise, the player loses. After playing this game many times, they discovered an important fact: for some randomly written sequences, no matter how you play, it is impossible to win. Such sequences are called “bad sequences”, and the other sequences are called “good sequences”. Although this game is very fun, it has one drawback: before each game, it takes a lot of time to write down the random sequence. This has always bothered them. Until the night before this year’s NOI Qualifier, Little L came up with an amazing idea and solved this problem at once. They first draw a huge unrooted tree (with $m$ nodes) on the paper, and write an integer on each node. When they want to play the game, the player just chooses any two nodes, finds the unique path connecting these two nodes, and lists the integers written on all nodes along the path (including both endpoints) in order of the path. This gives a sequence, and then they can play the game on this sequence. If the two endpoints are nodes $v_i$ and $v_j$, the obtained sequence is denoted briefly as $i\sim j$. Of course, as mentioned above, the sequence $i\sim j$ can also be either a “good sequence” or a “bad sequence”. They found this improvement really makes things much more convenient. Moreover, it brings some new fun to the game. For example, Little X claimed that he found an important rule: the property of sequences is transitive. That is, for any distinct $i,j,k$: - If $i\sim j$ is a good sequence and $j\sim k$ is a good sequence, then $i\sim k$ is a good sequence. - If $i\sim j$ is a bad sequence and $j\sim k$ is a bad sequence, then $i\sim k$ is a bad sequence. This conclusion is surprisingly elegant, but soon Little H found a counterexample, which made Little X feel upset. To comfort Little X, Little L said: why not see in how many cases your conclusion is true? Little X cheered up, and everyone threw themselves into the heavy work. They need to count how many triples $(i,j,k)$ with $i

The first line contains an integer $m$, the number of nodes in the unrooted tree. The next $m$ lines each contain two integers $f_i,x_i$, where $f_i

Output one integer in one line, the answer.

### Constraints For $10\%$ of the testdata, $1\leq m\leq 5$. For $30\%$ of the testdata, $1\leq m\leq 100$. For $50\%$ of the testdata, $1\leq m\leq 10^3$. For $100\%$ of the testdata, $1\leq m\leq 10^5$. Translated by ChatGPT 5