FIRE - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

Consider the following acyclic graph. The nodes are the bushes and two are adjacent if they are close enough to spread fire to each other. Consider
the component with the bush that caught on fire first and think of this as a tree rooted at node the burning bush. The input specification says each
node in this tree has at most two children. Now, let f(v) be a boolean function that is true if and only if it is possible to save the special bushes in the
subtree rooted at v if node v is on fire and no children of v are on fire. Then, f(v) satisfies the following recurrence:
f(v) = FALSE if v is a special tree
f(v) = TRUE if v has at most one child (since we can save that child before the fire spreads from v)
f(v) = f(u) OR f(w) (here OR is the logical or)
In this last case if f(u) = f(w) = FALSE, then since we can only save one of u or w before the flames leap from v, then we cannot save all special
bushes. Otherwise, say f(u) = TRUE (the other case is symmetric). We then save bush w from the flames leaping from v and allow bush u to catch
fire. Since f(u) is TRUE, we know that we can save the special bushes in the subtree rooted at u in later steps so we may use this step to save bush w.

2

Can I get some test cases please, I simply ran a DFS where if a node has at most one child than break and print “yes” else recurse to only those nodes which are not special bushes, if DFS is complete without finding a node with at most one child than output “no”, can somebody provide me testcases where my solution fails:

Here is my WA Solution