C++ 解法, 执行用时: 335ms, 内存消耗: 22576K, 提交时间: 2022-04-06 10:40:33

// USACO 2019 Jan P. Exercise Route
#include <bits/stdc++.h>
const int NN = 2e5 + 4;
using namespace std;
using VI = vector<int>;
VI G[NN];
int fa[NN][20], D[NN], Sum[NN], Sz[NN], HH;
void dfs(int u, int f, int d) {
  fa[u][0] = f, D[u] = d;
  for (int i = 1; (1 << i) <= d; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (int v : G[u])
    if (v != f) dfs(v, u, d + 1);
}
int lca(int u, int v) {
  if (D[u] < D[v]) swap(u, v);
  for (int i = HH; i >= 0; i--)
    if ((1 << i) & (D[u] - D[v]))
      // D[fa[u][i]] >= D[v])
      u = fa[u][i];
  if (u == v) return u;
  for (int i = HH; i >= 0; i--)
    if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
  return fa[u][0];
}
int topBelow(int u, int anc) {
  if (u == anc) return 0;
  for (int i = HH; i >= 0; i--)
    if (D[fa[u][i]] > D[anc]) u = fa[u][i];
  return u;
}
void dfs2(int u, int f, int s) {
  Sz[u] = s;
  for (int v : G[u])
    if (v != f) dfs2(v, u, s + Sum[v]);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, m;
  cin >> n >> m, HH = ceil(log2(n)) + 1;
  for (int i = 1, x, y; i <= n - 1; i++)
    cin >> x >> y, G[x].push_back(y), G[y].push_back(x);
  dfs(1, 0, 1);
  long long ans = 0;
  VI A(m + 1), B(m + 1);
  map<pair<int, int>, int> Q;
  for (int i = n; i <= m; i++) {
    cin >> A[i] >> B[i];
    int d = lca(A[i], B[i]), ta = topBelow(A[i], d), tb = topBelow(B[i], d);
    if (ta) ans -= ++Sum[ta];
    if (tb) ans -= ++Sum[tb];
    if (ta && tb) {
      if (ta > tb) swap(ta, tb);
      ans -= Q[{ta, tb}]++;
    }
  }
  dfs2(1, 1, 0);
  for (int i = n; i <= m; i++)
    ans += Sz[A[i]] + Sz[B[i]] - 2 * Sz[lca(A[i], B[i])];
  cout << ans << "\n";
  return 0;
}