```
class Solution {
public:
int rob(TreeNode* root) {
pair<int, int> p = dp(root);
return max(p.first, p.second);
}
pair<int, int> dp(TreeNode* root) {
if (!root) return {0, 0};
pair<int, int> left = dp(root->left), right = dp(root->right);
int include = root->val + left.second + right.second;
int exclude = max(left.first, left.second) + max(right.first, right.second);
return {include, exclude};
}
};
/**
* dp[n] means max amount of money the theif can rob begin with root n,
* include means max amount with robbing n, exclude means max amount without robbing n,
* so we get:
* dp[n] = max(include, exclude), in which:
* include = n + dp[n->left.exclude] + dp[n->right.exclude]
* exclude = dp[n->left] + dp[n->right]
**/
```