(Analysis by Spencer Compton )

Let's think about the pairs of non-standard trails that Bessie could use to make a good route. Consider the tree that consists of standard trails. We will think of a non-standard trail's "path" as the path between its two corresponding nodes in the aforementioned tree. If the two non-standard trails we are considering have edge-disjoint paths, then it is not possible to create a simple cycle with them. However, if their paths do overlap, then we can create exactly one simple cycle.

Now we have another problem, how do we count the pairs of non-standard trails whose paths overlap? We will consider the tree to be arbitrarily rooted. Let a non-standard trail go from node $A$ to node $B$ through its lowest common ancestor (LCA) $L$. This is a somewhat difficult shape to work with. What if we decided to instead break each nonstandard path into the path from $A$ to $L$ and the path from $L$ to $B$, and then counted the number of paths that overlap? With this method of counting, we may overcount. However, we can easily tell if a pair will be overcounted. We see that a pair will be overcounted only when both trails have paths that go through the same LCA and the two edges that are connected to the LCA in their path are the same. We can then just find the number of such pairs and remove this from our answer, as this allows us to ignore the overcounting and work with paths of a very simple shape.

Our problem is now simpler, we have paths that travel from some node to one of its ancestors and we want to count the number of pairs that overlap. A similar, more well-known problem is this but in the form of 1-dimensional line segments. A segment in the form [$A_i$,$B_i$] would mean there was a line that started at $A_i$ and ended at $B_i$. We could solve it in the following manner. At the start of every segment subtract from your answer the number of segments that began before it, while at the end of every segment add to your answer the number of segments that began before the end of this segment. (Being slightly careful about pairs of segments that start/end in the same location).

In the tree version, we can do the exact same thing. We can use precalculation with a depth-first search to calculate the number of paths that start at an ancestor of each node. Then for each path that goes from a node $A$ to an ancestor $B$, we add (the number of paths that start at an ancestor of $B$) - (the number of paths that start at an ancestor of $A$) to our answer. We are careful not to overcount pairs that have the same lowest edge on their path.

Below is Dhruv Rohatgi's implementation.


#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define MAXN 200000

int N,Q;
vector<int> edges[MAXN];
int x[MAXN], y[MAXN], anc[MAXN];
int p[MAXN][20];
int d[MAXN];

int numInters[MAXN];
int psInters[MAXN];
map<pair<int,int>, int> MP;

void dfs(int i,int par,int depth)
{
p[i][0] = par;
d[i] = depth;
for(int j=0;j<edges[i].size();j++)
if(edges[i][j]!=par)
dfs(edges[i][j],i, depth+1);
}

void dfsSum(int i, int ps)
{
psInters[i] = ps;
for(int j=0;j<edges[i].size();j++)
if(edges[i][j]!=p[i][0])
dfsSum(edges[i][j], ps + numInters[edges[i][j]]);
}

void precompute()
{
dfs(0, -1, 0);
for(int j=1;j<20;j++)
for(int i=0;i<N;i++)
{
if(p[i][j-1]==-1)
p[i][j] = -1;
else
p[i][j] = p[p[i][j-1]][j-1];
}
}

int lca(int a,int b)
{
for(int j=19;j>=0;j--)
if(d[p[a][j]] >= d[b])
a = p[a][j];
for(int j=19;j>=0;j--)
if(d[p[b][j]] >= d[a])
b = p[b][j];
for(int j=19;j>=0;j--)
if(p[a][j]!=p[b][j])
a = p[a][j], b = p[b][j];
if(a==b) return a;
return p[a][0];
}

int topEdge(int top,int bot)
{
if(top==bot)
return -1;
for(int j=19;j>=0;j--)
if(d[p[bot][j]] > d[top])
bot = p[bot][j];
return bot;
}

long long choose2(int m)
{
return (((long long) m)*(m-1))/2;
}

int main()
{
int M,a,b;
cin >> N >> M;
Q = M - (N-1);
for(int i=0;i<N-1;i++)
{
cin >> a >> b;
a--,b--;
edges[a].push_back(b);
edges[b].push_back(a);
}
precompute();
long long ans = 0;
for(int i=0;i<Q;i++)
{
cin >> x[i] >> y[i];
x[i]--,y[i]--;
anc[i] = lca(x[i],y[i]);
int topx = topEdge(anc[i], x[i]);
if(topx != -1)
{
ans -= numInters[topx] + 1;
numInters[topx]++;
}
int topy = topEdge(anc[i], y[i]);
if(topy != -1)
{
ans -= numInters[topy] + 1;
numInters[topy]++;
}
if(topx != -1 && topy != -1)
{
if(topx>topy) swap(topx,topy);
ans -= MP[make_pair(topx,topy)];
MP[make_pair(topx,topy)]++;
}
}
dfsSum(0,0);
for(int i=0;i<Q;i++)
ans += psInters[x[i]] + psInters[y[i]] - 2*psInters[anc[i]];
cout << ans << '\n';
}