Official

F - Tree Vertices XOR Editorial by antontrygubO_o

Firstly, let’s make a couple of quick observations.

  • The operation is equivalent to flipping the number in a node, if it has an odd number of neighbors with $1$ written in them.
  • The operation is reversible, so we will count, from how many configurations we can reach the configuration with all ones.
  • The parity of the number of connected components of $1$ doesn't change. Indeed: suppose we flip a node which has $x$ neighbors with $1$ written on them (where $x$ is odd). Then, by flipping it from $0$ to $1$, we will decrease the number of components by $x-1$, when flipping from $1$ to $0$ - increase by $x-1$. Therefore, the number of components of $1$ in the reachable configuration must be odd.
  • If every node has an even number of neighboring ones, it's impossible to perform any operation, so it's impossible to make all ones (note that in all ones we can do at least one operation: on any leaf).

We will prove the following statement.

Lemma. Suppose that the following \(3\) conditions hold:

  • The number of connected components of ones is odd $\ge 3$
  • We can do at least one operation (meaning that there exists a node such that odd number of its neighbors have $1$)
  • There exists a node with degree at least $3$, such that at least $2$ of its subtrees have size $\ge 2$.
Then by some sequence of operations, we can decrease the number of connected components of ones.
Proof (hard and a bit messy, I would be glad to hear yours if they are simpler and shorter) Firstly, note that we can compress any component of $1$s into a single node with $1$ and other nodes with $0$ (just by making one leaf at a time $0$). Let's do this compression, now no $2$ $1$s have a direct edge between them.

Secondly, note that we can do the following operations:
  • Merging operation. Choose a node $v$ with $0$ on it with odd $\ge 3$ number of neighbors with $1$ on them, replace all those by $0$s, and replace the $0$ in $v$ by $1$ (first apply operation to $v$, then to all neighbors in order).
  • Moving operation. Choose a node $u$ with $1$ on it, and move this $1$ to an adjacent node $v$ which doesn't have any other adjacent $1$s (first apply operation to $v$, then to $u$.

Suppose that the conditions of the lemma hold, but we can’t decrease the number of components.

Let \(v\) be this node with degree at least \(3\), such that at least \(2\) of its subtrees have size \(\ge 2\). Root the tree at it.

I will start by proving another Lemma.

Lemma 1: Consider any subtree of node \(u\) in this rooted tree (not considering other nodes). Then, it is possible to change the number written in \(u\) by doing only operations inside this subtree if and only if it’s possible to do at least one operation inside this tree.

Proof of Lemma 1 It's obvious that it's necessary that it's possible to make at least one operation. Now let's prove that it's sufficient.

We will prove this by induction. For subtrees of size $1$ it's obviously true.

Denote the children of $u$ as $x_1, x_2, ..., x_k$. Consider $2$ cases, depending on what's the number in $u$.

If $0$ is written in $u$:
  • If the number of children of $u$ with $1$ on them is even, apply our lemma and change one of them, now the number of such children is odd.
  • If there is exactly one child with $1$ on it, we can just move it to $u$.
  • If there is odd $\ge 3$ number of children with $1$, we can make a merging operation.
If $1$ is written in $u$:

We know that $x_1, \dots, x_k$ all contain zeros. If it's impossible to move $1$ from $u$ to any of these, it means that each $x_i$ has a child with $1$ in it. Also, if it's impossible to make a merging operation with any $x_i$, every $x_i$ should have an odd number of children with ones.

Consider any child in whose subtree we can do some operation, wlog x_1. Choose any subtree of of $x_1$ in which we can do some operation, and change the number in the root of that tree: now $x_1$ has even number of children with ones. So, now we can make a merging operation with $x_1$.

Lemma proved.

Now, let’s prove one more lemma.

Lemma 2: Consider a subtree with root \(u\) such that:

  • It contains at least $1$ one.
  • Number in $u$ is $0$.
  • It's impossible to make any operation in it.

Then, I will state the following: let’s append some node \(u_1\) with \(1\) on it as a leaf to \(u\). In this modified subtree, we can do a merge operation.

Proof of Lemma 2 Choose any node with $1$ in the subtree, say $v$, and start moving our $1$ from $u_1$ to it. At some point we won't be able to do this: suppose we won't be able to move $1$ to node $w$. This means that the number in $w$ is $0$ (as there is $1$ adjacent to it at the node from which we tried to move here).

Now let's consider possible number of ones in children of $w$.
  • If no children of $w$ have one in them - we would be able to move to $w$.
  • If exactly one child of $w$ has one in it, we would be able to make an operation with that child, by moving it to $w$ initially.
  • If odd $\ge 3$ number of children of $w$ have one in them, we would be able to merge there initially.
  • If even $\ge 2$ number of children of $w$ have one in them, we are able to merge now.
Proof completed.

Now, let’s get back to our problem. If the root \(v\) has \(1\) in it, change it to \(0\) (it’s possible by Lemma 1).

Now, let’s consider its children \(x_1, ..., x_k\) and correspondent subtrees. For every \(x_i\), if we can make the number in it \(1\) by some operations in its subtree, make it.

If at least \(3\) children now have \(1\) in them: if the number of children with \(1\) is odd, we can merge right away, else change the number in some child to get the odd case again.

So, we have \(1\) or \(2\) children with one in them (\(0\) is not possible, this would mean we can’t perform any operations). We will show that in both cases we can do some merge operation. Let’s consider both cases.

  • Suppose that exactly one child has one in it, wlog $x_1$. Note that no subtree of any other child can have ones. Indeed: if the subtree of $x_2$ has one, but it's impossible to make any operations there, we can move one from $x_1$ to $v$ and get the statement of Lemma 2: we will be able to do some merge operation.

    So, all the ones are in subtree of $x_1$. Consider child $x_2$ with size of subtree at least $2$. Then, move one from $x_1$ to $v$ and then to $x_2$. Now, note that we can still make some operations in the subtree of $x_1$ (else we would be able to apply Lemma 2), so make the number in $x_1$ one. We got the second case.

  • Suppose that we have exactly $2$ children with one in them, wlog in $x_1$ and $x_2$. Also, wlog we can make the number in $x_1$ zero (we can change the number in at least one child of $v$, but can't in any except $x_1, x_2$).

    Then, firstly, subtrees of all other $x_i$s are empty: otherwise we would be able to make the number in $x_1$ zero, move $x_2$ to $v$ and get Lemma $2$,

    Now, make number in $x_1$ zero, move one from $x_2$ to $x_3$. If it's still possible to make some operation in the subtree of $x_2$, we can make the number in $x_2$ one, in $x_1$ one, and will be able to merge. Otherwise, by Lemma 2, the subtree of $x_2$ is now empty (or, again, we would be able to merge there).

    Now, all children except $x_1$ are kinda interchangeable (as we can move one from $x_2$ to $v$). Wlog, size of subtree of $x_2$ is at least $2$. Then, move one from $x_2$ deeper into this subtree, then move one from $x_1$ to $x_3$. Note that we can still make some operations in the subtree of $x_1$, as otherwise we could apply Lemma 2. So, make number in $x_1$ one, make number in $x_2$ one again, and do the merge operation.

From the lemma it follows, that from any such configuration, we can reach the configuration with all ones, by reducing the number of connected components of ones to \(1\): then making all nodes \(1\) is trivial. So, for the case of the tree, for which there exists a node with degree at least \(3\), such that at least \(2\) of its subtrees have size \(\ge 2\), we just have to find the number of configurations with odd number of components of ones and with at least one possible move. This is easy to do with \(O(N)\) dp.

All other graphs have the following form: Chain with stars on the ends, and for them we have to calculate the answer separately. Let’s find the exact answer for the chain of length \(l\), with ends \(A\) and \(B\), such that \(A\) has additional \(x\) leaves, and \(B\) has additional \(y\) leaves.

Then, the following configurations are the only possible ones:

  • If both $A$ and $B$ have one on them, all nodes on the path from $A$ to $B$ has to have ones, and leaves can be chosen arbitrarily: this gives $2^{x+y}$ configurations.
  • If $A$ has one on it and $B$ has zero, then we can choose leaves of $A$ arbitrarily, even number of leaves of $B$ have to have ones, and some prefix of the chain has to have ones: this gives $2^x \cdot 2^{y-1} \cdot (len-1) = 2^{x+y-1}(len-1)$ configurations.
  • If $A$ has one on it and $B$ has zero, we get the same answer as in previous case: $2^x \cdot 2^{y-1} \cdot (len-1) = 2^{x+y-1}(len-1)$ configurations.
  • Finally, if both $A$ and $B$ have zeros on them, there are two families of configurations:
    1. Odd number of leaves have ones, all other nodes have zeros: this gives $2^{x+y-1}$ configurations.

    2. Even number of leaves of \(A\) have ones, even number of leaves of \(B\) have ones, some segment of chain has ones: this gives \(2^{x+y-2}\frac{(len-1)(len-2)}{2}\) configurations

The proof of this is left as an exercise to the reader.

posted:
last update: