DP解题思路： 画出leve1~5的图形之后就可以发现，level[i]是由1个level[i-1]和2个level[i-2]再加一个根节点组成的，以level[4]为例：红色的为level[3]，绿色的为level[2] 两种比较好的理解方式：
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int maxn = 2000000 + 1, mod = 1000000007; int n; long long dp[maxn] = {}; int main() { int T; scanf("%d", &T); for(int i = 3; i < maxn; ++ i) dp[i] = (dp[i - 1] + dp[i - 2] * 2 + (!(i % 3) ? 4 : 0)) % mod; while(T --) { scanf("%d", &n); printf("%d\n", dp[n]); } return 0; } #include <iostream> #include <algorithm> using namespace std; const int mod = 1e9+7; const int maxn = 2000010; long long dp[maxn][2] = {0}; void init(){ for(long long i = 3;i<maxn;i++){ dp[i][0] = (max(dp[i-2][0],dp[i-2][1])*2+max(dp[i-1][0],dp[i-1][1]))%mod; dp[i][1] = (dp[i-2][0]*2+dp[i-1][0]+4)%mod; } } int main(){ long long t; cin >> t; init(); while(t--){ long long n; cin >> n; cout << max(dp[n][0],dp[n][1]) << endl; } return 0; }最后一种方法是贪心得出的： 第i次增加的结点：a[i]=a[i-1]+2a[i-2] 答案：sum[i]=4a[i-2]+sum[i-3],可以用矩阵快速幂优化
#include <iostream> #include <cstring> #include <cstdio> #include <queue> #include <algorithm> #include <cmath> #include <vector> #include <map> using namespace std; #define inf 0x7fffffff #define ll long long #define mod (1000000007) ll a[2000006],sum[2000006]; int main(){ ll i, n, j, k, t, m; a[1]=1,a[2]=1; for(i=3;i<=2000007;i++){ a[i]=(a[i-1]+2*a[i-2])%mod; sum[i]=(4*a[i-2]+sum[i-3])%mod; } scanf("%lld",&t); while(t--){ scanf("%lld",&n); printf("%lld\n",sum[n]); } }