# Tutorial: Tree Rerooting approach for Path XOR Sums↵
↵
Hello everyone! I recently solved this problem and wanted to share a Tree Rerooting (In-Out DP) solution based on the contribution technique. ↵
Problem Link: [problem:766E]↵
↵
If you're looking for a structured way to handle path XOR queries across a tree, breaking it down into bits and using Tree DP is the way.↵
↵
### 1. The Contribution Technique↵
Instead of computing the XOR sum for every single path $d(x, y)$, we can process the answer bit by bit. Since, $a[i] <= 1e6$, 20 bits are enough.↵
↵
For a specific bit $b \in [0, 20]$, we can treat the node values $a_i$ as a binary sequence (either $0$ or $1$ depending on the $b$-th bit). ↵
Our goal for each bit $b$ reduces to: **Find the number of paths in the tree where the sum of the $b$-th bit is odd (i.e., XOR sum is $1$).**↵
↵
If we can find this count, let's call it $res(b)$, then our final answer is simply:↵
$$ \sum_{b=0}^{20} res(b) \cdot 2^b $$↵
↵
### 2. Downwards Tree DP (In-DP)↵
Let's root the tree arbitrarily (e.g., at node $1$). For a given bit $b$, let $a(u)$ be the value of the $b$-th bit of node $u$. We define our states:↵
*$c(u, 0) =$ number of paths starting at $u$ and going *down* into its subtree with an XOR sum of $0$*.↵
*$c(u, 1) =$ number of paths starting at $u$ and going *down* into its subtree with an XOR sum of $1$*.↵
↵
**Base Case:** ↵
A single node forms a valid path by itself.↵
$$ c(u, a(u)) = 1 $$↵
↵
**Transitions:** ↵
For every child $v$ of $u$, if a path from $v$ has a sum of $S$, extending it to $u$ makes the sum $S \oplus a(u)$. ↵
*To get a total sum of $0$, we need $S \oplus a(u) = 0 \implies S = a(u)$*.↵
*To get a total sum of $1$, we need $S \oplus a(u) = 1 \implies S = 1 \oplus a(u)$*.↵
↵
Therefore, we sum over all children $v$:↵
$$ c(u, 0) += \sum_{v \in child(u)} c(v, a(u)) $$↵
$$ c(u, 1) += \sum_{v \in child(u)} c(v, 1 \oplus a(u)) $$↵
↵
### 3. Upwards Tree Rerooting (Out-DP)↵
To get the paths that go *up* from $u$ (towards its parent and into other branches), we define:↵
*$up(u, 0) =$ number of paths starting at $u$ and going *up* with an XOR sum of $0$*.↵
*$up(u, 1) =$ number of paths starting at $u$ and going *up* with an XOR sum of $1$*.↵
↵
When transitioning from $u$ to its child $v$, the paths going "up" from $v$ consist of all valid paths starting at $u$ **except** the ones that go down into $v$'s subtree. ↵
↵
Let $x = a(v)$ and $y = a(u)$. The rerooting transitions are:↵
$$ up(v, 0) = up(u, x) + c(u, x) - c(v, x \oplus y) $$↵
$$ up(v, 1) = up(u, 1 \oplus x) + c(u, 1 \oplus x) - c(v, (1 \oplus x) \oplus y) $$↵
↵
*Explanation:* $up(u, x) + c(u, x)$ gives all paths starting at $u$ with XOR sum $x$. We subtract $c(v, x \oplus y)$ to remove the paths that strictly lie in $v$'s subtree. Adding $v$ to these paths toggles their sum by $x$, giving us the required $0$ or $1$ sum for $up(v, \dots)$.↵
↵
### 4. Assembling the Answer for Bit $b$↵
Once both DP passes are complete, the total number of paths starting at any node $u$ with an XOR sum of $1$ is $c(u, 1) + up(u, 1)$.↵
↵
However, if we simply sum this over all nodes:↵
$$ res(b) = \sum_{u \in V} \left( c(u, 1) + up(u, 1) \right) $$↵
↵
We will double-count every path of length $> 1$ (since it is counted once from each endpoint). Single-node paths (where $a(u) = 1$) are only counted once. ↵
↵
To fix this, we subtract the single-node paths, divide by 2, and then add the single-node paths back:↵
$$ res(b) = \sum_{u \in V} \left( c(u, 1) + up(u, 1) - (a(u) == 1) \right) $$↵
$$ res(b) /= 2 $$↵
$$ res(b) += \sum_{u \in V} (a(u) == 1) $$↵
↵
Finally, add $res(b) \cdot 2^b$ to your global answer! ↵
↵
Code for reference: [submission:387352291]↵
↵
***↵
↵
Hope this makes the In-Out DP logic clear.
↵
Hello everyone! I recently solved this problem and wanted to share a Tree Rerooting (In-Out DP) solution based on the contribution technique. ↵
Problem Link: [problem:766E]↵
↵
If you're looking for a structured way to handle path XOR queries across a tree, breaking it down into bits and using Tree DP is the way.↵
↵
### 1. The Contribution Technique↵
Instead of computing the XOR sum for every single path $d(x, y)$, we can process the answer bit by bit. Since, $a[i] <= 1e6$, 20 bits are enough.↵
↵
For a specific bit $b \in [0, 20]$, we can treat the node values $a_i$ as a binary sequence (either $0$ or $1$ depending on the $b$-th bit). ↵
Our goal for each bit $b$ reduces to: **Find the number of paths in the tree where the sum of the $b$-th bit is odd (i.e., XOR sum is $1$).**↵
↵
If we can find this count, let's call it $res(b)$, then our final answer is simply:↵
$$ \sum_{b=0}^{20} res(b) \cdot 2^b $$↵
↵
### 2. Downwards Tree DP (In-DP)↵
Let's root the tree arbitrarily (e.g., at node $1$). For a given bit $b$, let $a(u)$ be the value of the $b$-th bit of node $u$. We define our states:↵
*$c(u, 0) =$ number of paths starting at $u$ and going *down* into its subtree with an XOR sum of $0$*.↵
*$c(u, 1) =$ number of paths starting at $u$ and going *down* into its subtree with an XOR sum of $1$*.↵
↵
**Base Case:** ↵
A single node forms a valid path by itself.↵
$$ c(u, a(u)) = 1 $$↵
↵
**Transitions:** ↵
For every child $v$ of $u$, if a path from $v$ has a sum of $S$, extending it to $u$ makes the sum $S \oplus a(u)$. ↵
*To get a total sum of $0$, we need $S \oplus a(u) = 0 \implies S = a(u)$*.↵
*To get a total sum of $1$, we need $S \oplus a(u) = 1 \implies S = 1 \oplus a(u)$*.↵
↵
Therefore, we sum over all children $v$:↵
$$ c(u, 0) += \sum_{v \in child(u)} c(v, a(u)) $$↵
$$ c(u, 1) += \sum_{v \in child(u)} c(v, 1 \oplus a(u)) $$↵
↵
### 3. Upwards Tree Rerooting (Out-DP)↵
To get the paths that go *up* from $u$ (towards its parent and into other branches), we define:↵
*$up(u, 0) =$ number of paths starting at $u$ and going *up* with an XOR sum of $0$*.↵
*$up(u, 1) =$ number of paths starting at $u$ and going *up* with an XOR sum of $1$*.↵
↵
When transitioning from $u$ to its child $v$, the paths going "up" from $v$ consist of all valid paths starting at $u$ **except** the ones that go down into $v$'s subtree. ↵
↵
Let $x = a(v)$ and $y = a(u)$. The rerooting transitions are:↵
$$ up(v, 0) = up(u, x) + c(u, x) - c(v, x \oplus y) $$↵
$$ up(v, 1) = up(u, 1 \oplus x) + c(u, 1 \oplus x) - c(v, (1 \oplus x) \oplus y) $$↵
↵
*Explanation:* $up(u, x) + c(u, x)$ gives all paths starting at $u$ with XOR sum $x$. We subtract $c(v, x \oplus y)$ to remove the paths that strictly lie in $v$'s subtree. Adding $v$ to these paths toggles their sum by $x$, giving us the required $0$ or $1$ sum for $up(v, \dots)$.↵
↵
### 4. Assembling the Answer for Bit $b$↵
Once both DP passes are complete, the total number of paths starting at any node $u$ with an XOR sum of $1$ is $c(u, 1) + up(u, 1)$.↵
↵
However, if we simply sum this over all nodes:↵
$$ res(b) = \sum_{u \in V} \left( c(u, 1) + up(u, 1) \right) $$↵
↵
We will double-count every path of length $> 1$ (since it is counted once from each endpoint). Single-node paths (where $a(u) = 1$) are only counted once. ↵
↵
To fix this, we subtract the single-node paths, divide by 2, and then add the single-node paths back:↵
$$ res(b) = \sum_{u \in V} \left( c(u, 1) + up(u, 1) - (a(u) == 1) \right) $$↵
$$ res(b) /= 2 $$↵
$$ res(b) += \sum_{u \in V} (a(u) == 1) $$↵
↵
Finally, add $res(b) \cdot 2^b$ to your global answer! ↵
↵
Code for reference: [submission:387352291]↵
↵
***↵
↵
Hope this makes the In-Out DP logic clear.
