题解 | Y型树

这是一个数学问题，可以通过以下步骤解决：

1. 数学推导：设 n-1 个点分成三组，每组至少一个点每组点数的和为 n-1（除去分叉点）最大组的点数不能超过 (n-1)/3
2. 计算策略：使用等差数列求和公式计算部分结果通过快速幂计算逆元使用补集的思想避免复杂的组合数计算
3. 具体步骤：计算 k = (n-1)/3使用 sum 函数计算等差数列的和使用 calc 函数处理特殊情况最终结果通过几个部分相加得到

import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    
    static long modpow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    static long sum(long x) {
        x %= MOD;
        return x % MOD * (x + 1) % MOD * modpow(2, MOD-2) % MOD;
    }
    
    static long calc(long x) {
        long ret = sum(x/2) * 2 % MOD;
        if(x % 2 == 0) ret = (ret + MOD - x/2 % MOD) % MOD;
        return ret;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        n--;  // 除去分叉点
        long k = n/3;  // 最大组的点数
        long ans = 0;
        ans = (ans + calc(n-1) + MOD - calc(n-k-1)) % MOD;
        ans = (ans + MOD - sum(k) % MOD) % MOD;
        ans = (ans + k) % MOD;
        System.out.println(ans);
    }
}