Bessie the cow realizes she needs to exercise more in order to stay in good
shape. She needs your help selecting potential routes around the farm that she
can use for her morning jogging routine.

The farm is made up of \(N\) fields (\(1 \leq N \leq 2 \cdot 10^5\)), conveniently
numbered \(1 \ldots N\), and conveniently connected by a set of \(M\) bi-directional
trails (\(1 \leq M \leq 2 \cdot 10^5\)). Being creatures of habit, the cows tend
to use one particular subset of \(N-1\) trails for all of their daily movement
between fields -- they call these the "standard" trails. It is possible to
travel from any field to any other field using only standard trails.

To keep her morning jog interesting, Bessie decides that she should pick a route
that involves some non-standard trails. However, she is so comfortable with
using standard trails, she doesn't want to use too many non-standard trails on
her route. After some thought, she decides a good route is one that forms a
simple cycle (returning to its starting point, and not using any field more
than once) that contains exactly two non-standard trails.

Please help Bessie count the number of good routes she can use. Two
routes are considered the same if they involve the same set of trails.

Problem credits: Dhruv Rohatgi

Problem credits: Dhruv Rohatgi

The first line contains \(N\) and \(M\). Each of the next \(M\) lines contains two
integers \(a_i\) and \(b_i\) describing the endpoints of a trail. The first \(N-1\) of
these are the standard trails.

Output the total number routes Bessie might want to use.

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > January > Platinum