int ans(int N, int s){ if(s == 1) return 2*N-1; return 2 * (N / (s + 1)) - (N % (s+1) != s); } the C++ function above gives the answer. I'll type the outline of the solution later (it's only an outline because I don't know how to deal with the details )

Let's start by having a few observations, each observation will simplify the graph (and the problem) progressively. 1. we can forget the directions and treat this graph as a rooted tree. proof: just draw the graph and observe. note that the definition for $s$-electrified might change a little, but it's trivial enough so I'll omit the detail. 2. we can make every leaf a power plant, and every power plant a leaf in the tree. proof: every power plant must be a leaf, because its in degree is $0$, and out degree is at most one, meanwhile, if there's a leaf that isn't a power plant, it must be $0$-electrified, so it doesn't contribute to anything. Call a node a neck iff it has exactly one direct child. 3. we can remove each neck node, and connect its parent and child together. the number won't get smaller. proof: neck nodes are all $0$-electrified, so they're useless, and by connecting its parent and child together and erasing the neck node, every node that is s-electrified before will still be s-electrified after. Let the weight of each node be the number of leafs its subtree contains. For some node $v$, let its child be $c_1, c_2, \dots, c_k$, and their weights be $w_1 \ge w_2 \ge \dots \ge w_k$. Observe that, if we want to test whether $v$ is $s$-electrified, the best edge to remove is the edge between $v$ and $c_1$. so $$\textbf{v is s-electrified} \iff \sum_{i=2}^k w_i \ge s$$ The following claim is quite crucial. 4. there exists an optimal configuration such that the headquarter is s-electrified, or the answer is zero. proof: if the headquarter isn't s-electrified, $\sum_{i=2}^k w_i < s$, those other subtrees are practically useless, so we can remove them, and connect the isolated power plants to $c_1$, and make $c_1$ the new headquarter , and remove the original headquarter. This process does not decrease the answer, and it ends after repeated application. so we are done here. by using 4 on all nodes, we can have a even more useful property 5. there exists an optimal configuration such that all s-electrified node is connected. proof: above. From now on, we'll only consider the tree of s-electrified nodes. 6. if this tree has $a$ leafs and $b$ necks, then $N \ge a(s+1) + bs $ proof: for each leaf node, because it's $s$-electrified, it must have at least $s+1$ power plants connected to it. However for necks, because we'll remove its biggest child, it only needs $s$ power plants. 7. a tree with $a$ leafs and $b$ necks has at most $2a-b-1$ nodes proof: for each node that isn't leaf nor neck, we have to merge two leafs for it, so there can only be at most $a-1$ such nodes. 8. the optimal tree has at most one neck proof: if there's two necks, we just swap two necks out with one leaf, and we'll have a lot of power plants left over, so it's definitely better. therefore we'll prioritize making leafs, only try to make necks when we can't make leafs, some computation leads to the formula above, so we have an upper bound. The way to construct for upper bound is also described with 6. 7. 8. Therefore it's the final answer. $s = 1$ is a weird edge case which should be easy to deal with.

wayneyam wrote: Let's start by having a few observations, each observation will simplify the graph (and the problem) progressively. 1. we can forget the directions and treat this graph as a rooted tree. proof: just draw the graph and observe. note that the definition for $s$-electrified might change a little, but it's trivial enough so I'll omit the detail. 2. we can make every leaf a power plant, and every power plant a leaf in the tree. proof: every power plant must be a leaf, because its in degree is $0$, and out degree is at most one, meanwhile, if there's a leaf that isn't a power plant, it must be $0$-electrified, so it doesn't contribute to anything. Call a node a neck iff it has exactly one direct child. 3. we can remove each neck node, and connect its parent and child together. the number won't get smaller. proof: neck nodes are all $0$-electrified, so they're useless, and by connecting its parent and child together and erasing the neck node, every node that is s-electrified before will still be s-electrified after. Let the weight of each node be the number of leafs its subtree contains. For some node $v$, let its child be $c_1, c_2, \dots, c_k$, and their weights be $w_1 \ge w_2 \ge \dots \ge w_k$. Observe that, if we want to test whether $v$ is $s$-electrified, the best edge to remove is the edge between $v$ and $c_1$. so $$\textbf{v is s-electrified} \iff \sum_{i=2}^k w_i \ge s$$ The following claim is quite crucial. 4. there exists an optimal configuration such that the headquarter is s-electrified, or the answer is zero. proof: if the headquarter isn't s-electrified, $\sum_{i=2}^k w_i < s$, those other subtrees are practically useless, so we can remove them, and connect the isolated power plants to $c_1$, and make $c_1$ the new headquarter , and remove the original headquarter. This process does not decrease the answer, and it ends after repeated application. so we are done here. by using 4 on all nodes, we can have a even more useful property 5. there exists an optimal configuration such that all s-electrified node is connected. proof: above. From now on, we'll only consider the tree of s-electrified nodes. 6. if this tree has $a$ leafs and $b$ necks, then $N \ge a(s+1) + bs $ proof: for each leaf node, because it's $s$-electrified, it must have at least $s+1$ power plants connected to it. However for necks, because we'll remove its biggest child, it only needs $s$ power plants. 7. a tree with $a$ leafs and $b$ necks has at most $2a-b-1$ nodes proof: for each node that isn't leaf nor neck, we have to merge two leafs for it, so there can only be at most $a-1$ such nodes. 8. the optimal tree has at most one neck proof: if there's two necks, we just swap two necks out with one leaf, and we'll have a lot of power plants left over, so it's definitely better. therefore we'll prioritize making leafs, only try to make necks when we can't make leafs, some computation leads to the formula above, so we have an upper bound. The way to construct for upper bound is also described with 6. 7. 8. Therefore it's the final answer. $s = 1$ is a weird edge case which should be easy to deal with. The weird edge case $s=1$ does not occur if we assume that no power plants are $1$-electrified, so it would be fine.

Related: https://artofproblemsolving.com/community/c6h2918849p26078988