First problem:

void dfs(int v, int p, int c) {
    if (c) {
        answer.push_back(v);
    }
    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v, c ^ 1);
    }
    if (!c) {
        answer.push_back(v);
    }
}

Second problem:

You want to write A (the input) as a sum / subtraction of powers of four. Then it's a natural step to write A in base 4. If we could only add weights to one side of the scale, knowing the optimal number of weights would be simple: just sum all digits of A. Subtractions are annoying, so instead of using subtractions, let's introduce an alternate inversion operation by which you can invert a contiguous sequence of digits (by invert, I mean digit = 3-digit) of the number.

For example, this is 182 in base 4: 2312

Then we can use "invert" in the two middle digits to get: 2022

You can perform an inversion by adding two weights on the scale: an inversion from digit x to digit y is equivalent to adding 4^x + 1 - 4^y. We can see that inverting two overlapping segments is always equivalent to inverting two nonoverlapping segments (or sometimes zero if the segments are coincident), so the number of ways to make A is the number of ways to select nonoverlapping segments to invert such that the overall cost to make the number is minimum. This is a problem that can solved by a DP.