题目链接

题意

给定一棵 $NN$ 个节点的树，求解二元组 $(u,v)(u,\; v)$ 的个数，其中 $u,vu,\; v$ 是俩不相交的简单路径。

路径 $(i,j)(i,\; j)$ 与 $(j,i),i\mathrm{\ne }j(j,\; i),\; \backslash ,i\; \backslash ne\; j$ 视作同一路径。

制约

$N\in [1,2\times 10^5]N\; \backslash in\; [1,\; 2\; \backslash times\; 10\; ^\; 5]$

解答

显然，树上的路径均为简单路径,。容易知道 $NN$ 个节点的树的简单路径条数为：

而 $(i,j)(i,\; j)$ 与 $(j,i),i\mathrm{\ne }j(j,\; i),\; \backslash ,i\; \backslash ne\; j$ 视作一样的也没关系，求出所有二元组后除以二即可。

另一方面，所求也等价于 $((F(N{)}^2-\backslash Big((F(N)\; ^\; 2\; -$ 相交组数 $)\backslash Big)$，设两条路径交于 $uu$，即选择

讨论 $x,yx,\; y$ 的来源：

1. $x\in ux\; \backslash in\; u$，即 ${\mathrm{c}\mathrm{n}\mathrm{t}}_1=F(u)-{\displaystyle \sum _{to\in u}F(to)}\backslash mathrm\{cnt\}\_1\; =\; F(u)\; -\; \backslash displaystyle\; \backslash sum\_\{to\; \backslash ;\backslash in\backslash ;u\}\; F(to)$。
2. $x\mathrm{\notin }ux\; \backslash notin\; u$，即 ${\mathrm{c}\mathrm{n}\mathrm{t}}_2={\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}_u\times (n-{\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}_u)\backslash mathrm\{cnt\}\_2\; =\; \backslash mathrm\{size\}\_u\; \backslash times\; (n\; -\; \backslash mathrm\{size\}\_u)$。

注意不能是两点均来自 $x\mathrm{\notin }ux\; \backslash notin\; u$。组合起来：

参考代码

注：其中 Z 为 jiangly 的整数模板类。

Z f(int n) { return 1LL * n * (n + 1) / 2; }

void solve() {
  int n;
  std::cin >> n;

  std::vector<std::vector<int>> G(n);

  for (int i = 1, u, v; i < n; ++i) {
    std::cin >> u >> v;
    -- u, -- v;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  Z ans = f(n) * f(n);
  std::vector<int> size(n);

  std::function<void(int, int)> dfs = [&](int u, int p) {
    size[u] = 1;
    for (auto &&to : G[u]) if (to != p) {
      dfs(to, u);
      size[u] += size[to];
    }

    Z cnt1 = f(size[u]);
    Z cnt2 = 1LL * size[u] * (n - size[u]);

    for (auto &&to : G[u]) if (to != p) {
      cnt1 -= f(size[to]);
    }

    ans -= (cnt1 + cnt2) * (cnt1 + cnt2) - cnt2 * cnt2;
  };

  dfs(0, -1);

  std::cout << ans / 2 << '\n';
}

后寄

注：官方题解：

LCA 是什么东西，不是很懂，长大了再学。