566. The Best Set With No Two Neighbours
Each node of a tree holds a value. Choose a set of nodes with NO two of them joined by an edge, and print the largest total value such a set can have.
4 nodes, values 3 2 1 5, edges 1-2 1-3 3-4 -> 8 nodes 1 and 4
5 nodes in a star, values 10 1 1 1 1 -> 10 the centre alone beats all four leaves
## The array version, and why a tree is different
On a line this is the familiar "no two adjacent" scan: at each position, either take it and skip the one before, or skip it. One number per position is enough because a position has one predecessor.
A node has many children, so there is no single "the one before". What survives is the QUESTION, not the loop: for each node, was the node itself taken or not?
## Two numbers per node
take[u] = the best total in u's subtree, with u itself chosen
skip[u] = the best total in u's subtree, with u itself not chosen
If u is taken, no child may be taken, so each child contributes skip:
take[u] = value[u] + sum over children c of skip[c]
If u is not taken, each child is free either way, so each contributes its better option:
skip[u] = sum over children c of max(take[c], skip[c])
The answer is max(take[root], skip[root]).
Notice that the children are INDEPENDENT of one another. Two nodes in different subtrees are never adjacent, so no choice in one constrains the other. That independence is what makes a sum over children correct, and it is the property every problem in this topic relies on.
## Why one number per node is not enough
Storing only "the best in this subtree" loses the information the parent needs. The parent cannot use a child's best total without knowing whether that total used the child itself.
This is the same lesson as the take-or-skip states in the linear topic, and it is the first thing to check when a tree DP overcounts: the state must record whatever the parent is not allowed to ignore.
## Children first
A node's two numbers are read by its parent, so children must be finished first. Build a traversal order from the root with a stack, then walk that order BACKWARDS: every node is reached before its children in the forward order, so every node is reached after its children in the reverse.
Plain recursion is correct and will overflow the call stack on a path of 100000 nodes, which the constraints allow.
## Boundaries
A single node answers its own value, so n = 1 answers 7 when the value is 7. That case has
no edge lines at all, and a reader that insists on reading n - 1 lines is fine because
there are zero of them.
An edge joining the two largest values forces the choice: values 4 9 on one edge answer 9.
## Cost
Time O(n). Space O(n).
Totals reach 100000 times 10^9, so accumulate in 64 bits.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ each value ≤ 10^9` - the input is always a tree
Input
The first line contains an integer n, the number of nodes.
The second line contains n integers, where the ith is the value at node i.
Each of the next n - 1 lines contains two integers u and v, an edge of
the tree. Nodes are numbered 1 to n and the tree is rooted at node 1.
Output
Print one integer, the largest total value of a set with no two adjacent nodes.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.