Given a tree rooted at node $$$1$$$, each node $$$i$$$ has value $$$a_i$$$, let $$$s(u)$$$ denote the set of nodes in $$$u$$$'s subtree. You should calculate the sum: $$$\sum_u{(XOR_{c\in s(u)}(a_c+d(u,c)))}$$$.

I have reduced the problem to:

• Add 1 to every number on a segment.

• Find XOR on a segment.

But I can't think of any DS that solves the problem above. Any help will be appreciated.