**PROBLEM LINK**:

Practice

Contest, div. 1

Contest, div. 2

**Author:** Ashish Gupta

**Tester:** Zhong Ziqian

**Editorialist:** Oleksandr Kulkov

**DIFFICULTY**:

SIMPLE

**PREREQUISITES**:

DFS

**PROBLEM**:

You’re given tree on N vertices, each node has assigned value A_i. You may choose any node in the tree and remove all its descendants and the node itself. Your profit for that will be equal to the sum of values still existing in the tree minus X \cdot k where k is number of deletions and X is given number. You have to find the maximum possible profit.

**QUICK EXPLANATION**:

As simple as dp_v = \max\left(A_v+\sum\limits_{u \in \text{children}_v} dp_u, -X\right).

**EXPLANATION**:

Maintain dp_v to be best possible sum you may get from subtree of v. You will either drop subtree or not, in first case it’s -X and in second case it’s A_v plus sum of dp_u over all children of v:

```
int dfs(int v = 1, int p = 1) {
int res = 0;
for(auto u: g[v]) {
if(u != p) {
res += dfs(u, v);
}
}
return max(A[v] + res, -x);
}
```

**AUTHOR’S AND TESTER’S SOLUTIONS**:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.