题解 | #小红的二叉树#

中心节点枚举法

在树（无环连通图）中，任意两个度数大于等于 2 的节点之间都存在路径。对于长度为 2 的路径 ，节点 是该路径唯一的“中间节点”或“转折点”。

因此，可以将“计算所有长度为 2 的路径数量”转化为： 遍历树中每一个节点 ，计算以 为中心（中点）能组成多少条路径。

假设节点 的度数（连接的边数）为 ，要形成以 为中点的长度为 2 的路径，我们需要从 的邻居节点中选出 2 个不同的节点。 根据组合数学，以 为中点的路径数为：

问题的解即为所有节点贡献的总和：

基于上述模型，我们不需要遍历节点，只需根据满二叉树的拓扑性质，将节点分类并计算各类节点的数量及度数。

节点拓扑分类

在一棵深度为 的满二叉树中，节点可以严格分为三类：

1. 根节点 (Root)

   • 数量：1 个。
   • 位置：第 1 层。
   • 连接情况：无父节点，有 2 个子节点。
   • 度数 ()：2。
   • 贡献路径数：。path: (左子-根-右子)。

2. 叶子节点 (Leaf Nodes)

   • 数量： 个。
   • 位置：第 层。
   • 连接情况：有 1 个父节点，无子节点。
   • 度数 ()：1。
   • 贡献路径数：。叶子无法作为长度为 2 路径的中点。

3. 内部节点 (Internal Nodes)

   • 定义：既不是根也不是叶子的节点。
   • 位置：第 层 到 第 层。
   • 存在条件：仅当 时存在。
   • 数量计算：总节点数 - 根节点数 - 叶子节点数
   • 连接情况：有 1 个父节点，2 个子节点。
   • 度数 ()：3。
   • 贡献路径数：。paths: (父-本-左), (父-本-右), (左-本-右)。

通项公式推导

当 时，总路径数 为：

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll MOD = 1e9 + 7;

ll power(ll base, ll exp) {
    base %= MOD;
    ll sum = 1LL;

    while (exp > 0) {
        if (exp % 2 == 1) {
            sum = (sum * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }

    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    ll n;
    cin >> n;

    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = (3LL * power(2LL, n - 1) % MOD - 5 + MOD) % MOD;
    cout << ans << endl;
}