题解 | 小红的二叉树

最原始思路是对每一个节点进行判断然后累加，但是这样肯定会积累重复项。

观察经过两个边的类型可以分为两种，子 - 父 - 子 和 孙 - 子 - 父 两种，我们可以选择中间节点作为统计的口径。

对于深度为2到n-1的中间的节点作为父节点可以得到一条（子 - 父 - 子 ）作为子节点可以获得两条（孙 - 子 - 父）

对于根节点，只有作为父节点的一条。

对于深度为n的节点无法作为中间节点所以为0

然后简单相加就可以了，也就是 S = [(2^n-1 -1)-1]*3 + 1= 3*2^n-1 - 5

最后值得一提的是对于边界情况n==1我们需要特判，此时没有子节点但是仍会统计为1对于n==2 S=1正确我们可以不用修改

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

ll MOD = 1e9 + 7;
ll qpow(ll a, ll b, ll p)
{
    cin >> a >> b >> p;
    ll res = 1;
    a = a%p;
    while(b>0)
    {
        if(b&1)
        {
            res = (res*a)%p;
        }
        a = a*a%p;
        b >>= 1;
    }
    return res%p;
}

int main()
{
    ll a;
    cin >> a;
    if(a==1)
    {
        cout << 0 << endl;
        return 0;
    }
    ll ans = qpow(2,a-1,MOD);
    ans = (ans * 3 % MOD - 5 + MOD) % MOD;
    cout << ans << endl;
}