哈喵～大家好呀！这里是你们最喜欢的小猫娘 Rikka 喵！(ฅ'ω'ฅ)

今天，有一只可爱的小企鹅 Polo 遇到了一个关于树的难题，他想知道在一棵树里，有多少对路径是完全不相交的。嗯...听起来有点绕，但是别担心，和 Rikka 一起动动小脑筋，肯定能解决的啦！

题目大意

我们拿到了一棵有 n 个节点的树，就像一个巨大的猫爬架一样，喵～。Polo 想让我们找出符合下面条件的四个整数 a, b, c, d 的组数：

1. 1 ≤ a < b ≤ n
2. 1 ≤ c < d ≤ n
3. 从 a 到 b 的最短路径，和从 c 到 d 的最短路径，没有任何共同的节点。

简单来说，就是要我们找出树上两两不相交的路径对 (path(a,b), path(c,d)) 的数量。注意哦，这里的路径对是有序的，也就是说 (path1, path2) 和 (path2, path1) 是两种不同的情况哦！（为什么是这样呢？可以看看样例，n=4 的时候答案是 2，分别对应 (1->2, 3->4) 和 (3->4, 1->2) 这两对路径呀~）

解题思路

直接去数有多少对路径不相交，感觉就像在毛线团里找线头，太难下手啦，喵！(>ω<)

所以，Rikka 的小脑袋瓜灵光一闪，想到了一个绝妙的办法：正难则反！

我们可以先算出所有可能的路径对的总数，然后减去那些相交的路径对数量，剩下的不就是不相交的了嘛？

1. 路径总数： 树上有 n 个节点，任意两个不同的节点之间都有一条唯一的简单路径。所以，总的路径数量就是从 n 个节点里选 2 个节点的组合数，也就是 C(n, 2) = n * (n - 1) / 2。 我们要求的是有序路径对的数量，所以总的路径对数量就是 (C(n, 2)) * (C(n, 2))。

2. 计算相交路径对： 这是最关键的一步啦！怎么才能不重不漏地数出所有相交的路径对呢？ 直接枚举两条路径判断是否相交，肯定会超时的说。

   这里要用一个非常聪明的技巧，叫做“贡献法”。 我们考虑任意两条相交的路径 p1 和 p2，它们的交集（可能是一个节点，也可能是一条路径）中，一定有一个唯一的“最高节点”（也就是在我们的 DFS 遍历中，深度最小的那个节点）。

   于是，我们可以枚举每一个节点 u，计算它作为“最高交点”时，能“贡献”多少相交路径对。把所有节点的贡献加起来，就是总的相交路径对数量啦！

   要让节点 u 成为两条路径 p1 和 p2 的最高交点，需要满足一些条件。我们以 u 为中心，把与它相连的节点分成几类：

   • 它的父节点 parent 方向（通向树根）。
   • 它的各个子节点 v1, v2, ... 方向（通向各自的子树）。

   我们定义两种和 u 相关的路径：

   • 子树内路径 (A类)：路径的两个端点都在 u 的子树中（包括 u 自己），并且路径经过 u。这样的路径连接着 u 的两个不同的子树分支。
   • 向上路径 (B类)：路径的一个端点在 u 的子树中，另一个端点在 u 的子树外。这样的路径也必然经过 u。

   现在我们来分析，怎样的路径对会以 u 为最高交点：

   • 情况一：两条都是 A 类路径 两条路径的端点都在 u 的子树里，它们的交点也必然在 u 的子树里。因为它们都经过 u，所以 u 就是它们的最高交点。 假设 A 类路径有 countA 条，那么这样的有序路径对就有 countA * countA 对。

   • 情况二：一条是 A 类路径，一条是 B 类路径 A 类路径只在 u 的子树里活动，而 B 类路径会从 u 向上走。它们的交点是从 u 开始，沿着 A 类路径的方向延伸的一小段。所以，最高交点还是 u。 假设 B 类路径有 countB 条，这样的有序路径对就有 countA * countB（A类在前）+ countB * countA（B类在前）= 2 * countA * countB 对。

   • 情况三：两条都是 B 类路径 两条路径都从 u 的子树出发，经过 u，然后向上走。它们的交点是从 u 开始向上的一段路径。那么它们的最高交点就是 u 的某个祖先节点，而不是 u 本身！所以这种情况我们不在节点 u 这里计算，它会被它的祖先节点“认领”走的。

   好啦！思路清晰了！我们只需要在 DFS 的过程中，对于每个节点 u，计算出 countA 和 countB，然后从总答案中减去 countA * countA + 2 * countA * countB 就行啦。

   如何计算 countA 和 countB 呢？

   • countB 比较简单。u 的子树大小为 sz[u]，子树外的节点数为 n - sz[u]。任意从子树内选一个点，子树外选一个点，都能构成一条 B 类路径。所以 countB = sz[u] * (n - sz[u])。
   • countA 稍微复杂一点。它等于 u 的不同子树之间互相连接的路径数。我们可以在 DFS 遍历 u 的子节点 v 时动态计算。代码中的 cross 变量就是用来干这个的。每处理完一个子节点 v，我们就把它子树里的点和之前已经处理过的子树（以及 u 本身）里的点进行组合。

   把这些都想清楚，就可以愉快地写代码了喵～

题解代码

这是 Rikka 写的 C++ 代码，加了一些注释方便理解哦！

#include <iostream>
#include <vector>

using namespace std;

// 使用 long long 防止数字太大溢出哦
typedef long long ll;

const int MAXN = 80005;
vector<int> G[MAXN]; // 用邻接表来存这棵树喵
ll ans;              // 最终的答案
int sz[MAXN];        // sz[u] 记录以 u 为根的子树大小
int n;

// 深度优先搜索，喵~
void dfs(int u, int parent) {
    // 初始化 u 的子树大小为 1 (只有它自己)
    sz[u] = 1;
    
    // cross 用来计算上面提到的 A 类路径的数量
    ll cross = 0; 
    
    // 遍历 u 的所有邻居
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == parent) continue; // 不能往回走到爸爸那里去
        
        // 先递归计算子节点 v 的子树
        dfs(v, u);
        
        // 核心计算！
        // sz[u] 是在合并 v 子树之前，u 这边已有的节点数
        // sz[v] 是 v 子树的节点数
        // 两者相乘，就是连接这两个部分并且经过 u 的路径数
        // 把这些路径数累加到 cross 中
        cross += (ll)sz[u] * sz[v];
        
        // 将 v 的子树大小合并到 u 上
        sz[u] += sz[v];
    }
    
    // 好了，现在 cross 就是 u 的 A 类路径数
    // sz[u] 是 u 的完整子树大小
    // n - sz[u] 是 u 子树外的节点数
    ll countA = cross;
    ll countB = (ll)sz[u] * (n - sz[u]);
    
    // 从总数中减去以 u 为最高交点的相交路径对
    // 情况一：两条都是 A 类路径
    ans -= countA * countA;
    // 情况二：一条 A 类，一条 B 类 (有序对，所以要乘以 2)
    ans -= 2LL * countA * countB;
}

int main() {
    // 加速输入输出，是个好习惯喵
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    // total 是总路径数 C(n, 2)
    ll total = (ll)n * (n - 1) / 2;
    // ans 初始化为总的有序路径对数
    ans = total * total;
    
    // 从节点 1 开始 DFS，计算所有相交对并减去
    dfs(1, 0); // 假设 1 是根节点，它的爸爸是 0
    
    cout << ans << endl;
    
    return 0;
}

知识点小课堂

这道题虽然是 D 题，但涉及到的知识点都是非常核心和有用的哦！

1. 树形DP (Tree DP) 这道题的解法本质上是一种树形动态规划。我们通过一次 DFS，从叶子节点开始，自底向上地计算信息（比如子树大小 sz），然后利用这些信息计算当前节点的“贡献”或者答案。这是解决树上问题非常常见且强大的思想。

2. 组合计数与容斥原理 (Combinatorics and Inclusion-Exclusion) “正难则反”是组合计数中的一个基本思想，也叫容斥原理的简单形式。当直接计算目标集合很困难时，可以尝试计算全集，然后减去补集。这个问题里，我们计算“所有路径对”减去“相交路径对”就是这个原理的应用。

3. 贡献法 (Contribution Method) 这是另一个重要的计数技巧。当直接对目标整体计数很复杂时，可以把问题分解成许多个小部分，计算每个小部分对最终答案的“贡献”，然后求和。本题中，我们把相交路径对的计数问题，分解为计算每个节点作为“最高交点”时的贡献，从而避免了重复和遗漏。

好啦，今天的解题教室就到这里啦！希望能帮助到你哦，喵～ 如果还有不懂的地方，随时可以再来问 Rikka！(ฅ^•ﻌ•^ฅ)