```
public int numWays(int n, int k) {
if(n < 1) return 0;
int sum1 = k, sum2 = 0;
while(--n > 0){
int temp = sum2;
sum2 = sum1;
sum1 = (sum1 + temp) * (k - 1);
}
return sum1 + sum2;
}
```

At a first glance, I just gave it a k * (int)Math.pow(n-1, k-1), until I saw the n=2 & k=1 wrong answer, and found it interesting. It's actually a DP problem, where sum1 is computing not same color in current node, and sum2 is painting the same color currently.