Gardener-painter (Editorial)

Solution

For the first tree, we have $3$ ways to paint it. For the remaining trees, we have exactly 2 possibilities each, because we have to assign a different color from the previous one.

The answer is: $3\cdot 2^{n-1}$.

Time complexity: $O(n)$.

void solve(){
    int n;
    cin >> n;

    long long ans = 3;
    for(int i = 2; i <= n; i++){
        ans *= 2;
    }
    cout << ans << '\n';
}