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: 766E - Mahmoud and a xor trip

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] \lt = 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:

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.

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$$$:

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:

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:

We will double-count every path of length $$$ \gt 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:

Finally, add $$$res(b) \cdot 2^b$$$ to your global answer!

Code for reference:

#include <bits/stdc++.h>
using namespace std;
 
#define fastio() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
 
#define int long long
#define double long double
 
typedef long long ll;
typedef unsigned long long ull;
 
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
 
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define endl '\n'
 
#define IN_VEC(v,n) vector<int> v(n); for(auto &i : v) cin >> i;
#define IN_ARR(arr,n) for(int i=0;i<n;i++) cin >> arr[i];
 
const ll INF = 1e18;
const int MOD = 1e9 + 7;
void dfs(int u,int p,int b,vector<vi> &dp,vector<vi> &a,vector<vi> &adj){
	dp[a[b][u]][u]=1;
	for(int v:adj[u]){
		if(v==p) continue;
		dfs(v,u,b,dp,a,adj);
		dp[0][u] += dp[a[b][u]][v];
		dp[1][u] += dp[1-a[b][u]][v];
	}
}
void updp(int u,int p,int b,vector<vi> &dp,vector<vi> &up,vector<vi> &a,vector<vi> &adj){
	for(int v:adj[u]){
		if(v==p) continue;
		up[0][v] += up[a[b][v]][u] + dp[a[b][v]][u]-dp[a[b][v]^a[b][u]][v];
		int t=1-a[b][v];
		up[1][v] += up[t][u] + dp[t][u]-dp[t^a[b][u]][v];
		updp(v,u,b,dp,up,a,adj);
	}
}
void solve() {
    int n;
    cin>>n;
    vector<vi> a(20,vi(n,0));
    for(int i=0;i<n;++i){
    	int x;
    	cin>>x;
    	for(int j=0;j<20;++j){
    		if(x&(1ll<<j)) a[j][i]=1;
    	}
    }
    vector<vi> adj(n);
    for(int i=0;i<n-1;++i){
    	int u,v;
    	cin>>u>>v;
    	u--,v--;
    	adj[u].pb(v);
    	adj[v].pb(u);
    }
    int ans=0;
    vector<vi> dp,up;
    for(int b=0;b<20;++b){
    	dp.assign(2,vi(n,0ll));
    	up.assign(2,vi(n,0ll));
    	dfs(0,-1,b,dp,a,adj);
    	updp(0,-1,b,dp,up,a,adj);
    	int cnt=0;
    	for(int i=0;i<n;++i) cnt += dp[1][i] + up[1][i]-(a[b][i]==1);
    	cnt/=2;
    	for(int i=0;i<n;++i) if(a[b][i]==1) cnt++;
    	ans += (1ll<<b)*cnt;
    	dp.clear();
    	up.clear();
    }
    cout<<ans<<endl;
}
 
int32_t main() {
    fastio();
    solve();
    return 0;
}

Hope this makes the In-Out DP logic clear.

1. Count no. of hills in an array a, i.e. # no. of triplets (i,j,k) s.t. i<j<k & a[i]<=a[j]>=a[k]

Solution:

#include <bits/stdc++.h>
using namespace std;

#define fastio() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

#define int long long
#define double long double

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define endl '\n'

#define IN_VEC(v,n) vector<int> v(n); for(auto &i : v) cin >> i;
#define IN_ARR(arr,n) for(int i=0;i<n;i++) cin >> arr[i];

const ll INF = 1e18;
const int MOD = 1e9 + 7;
vi t1;
void update(int pos,int x,int lx,int rx){
    if(lx==rx-1){
        t1[x]+=1ll;
        return;
    }
    int mid=(lx+rx)/2;
    if(pos<mid) update(pos,2*x+1,lx,mid);
    else update(pos,2*x+2,mid,rx);
    t1[x]=t1[2*x+1]+t1[2*x+2];
}
int sum(int x,int lx,int rx,int l,int r){
    if(r<=lx || l>=rx) return 0;
    if(l<=lx && rx<=r) return t1[x];
    int mid=(lx+rx)/2;
    return sum(2*x+1,lx,mid,l,r)+sum(2*x+2,mid,rx,l,r);
}
void solve() {
    // 1. Hills - # (i,j,k) st i<j<k & a[i]<a[j]>a[k]
    int n;
    cin>>n;
    IN_VEC(a,n);
    // compress a st 0<=a[i]<=n-1
    vi rank=a;
    sort(all(rank));
    rank.erase(unique(all(rank)),rank.end());
    for(int i=0;i<n;++i){
        a[i]=lower_bound(all(rank),a[i])-rank.begin();
    }
    // we build two segment trees l,r intialised as 0
    t1.assign(n,0ll);
    vi l(n),r(n);
    for(int i=0;i<n;++i){
        l[i]=sum(0,0,n,0,a[i]);
        update(a[i],0,0,n);
    }
    t1.clear();
    t1.assign(n,0ll);
    for(int i=n-1;i>=0;--i){
        r[i]=sum(0,0,n,a[i]+1,n);
        update(a[i],0,0,n);
    }
    int ans=0;
    for(int i=0;i<n;++i){
        ans += l[i]*r[i];
    }
    cout<<ans<<endl;
}

int32_t main() {
    fastio();
    solve();
    return 0;
}

2. Let there be an array of N integers. You need to sum of (AND , OR) of all subarrays. Solution:

#include <bits/stdc++.h>
using namespace std;

#define fastio() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

#define int long long
#define double long double

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define endl '\n'

#define IN_VEC(v,n) vector<int> v(n); for(auto &i : v) cin >> i;
#define IN_ARR(arr,n) for(int i=0;i<n;i++) cin >> arr[i];

const ll INF = 1e18;
const int MOD = 1e9 + 7;

void solve() {
    // Let there be an array of N integers.
    //You need to sum of (AND , OR) of all subarrays.
    // i will use dp for this
    int n;
    cin>>n;
    IN_VEC(a,n);
    vector<vi> t(32,vi(n,0));
    for(int i=0;i<n;++i){
        for(int j=0;j<32;++j){
            if(a[i]&(1ll<<j)) t[j][i]=1;
        }
    }
    int res=0;
    for(int b=0;b<32;++b){
        int ans=0;
        // 1. let cnt1[i] be # j's st j<i & sum[j,i)>0
        vi cnt1(n+1,0ll), cnt2(n+1,0ll);
        for(int i=1;i<=n;++i){
            if(t[b][i-1]) cnt1[i]=i;
            else cnt1[i]=cnt1[i-1];
        }
        // 2. let cnt2[i] be # j's st j<i & sum[j,i)==j-i
        for(int i=1;i<=n;++i){
            if(t[b][i-1]) cnt2[i]=cnt2[i-1]+1ll;
            else cnt2[i]=0ll;
        }
        for(int i=0;i<n;++i){
            if(t[b][i]) ans+= i+2ll+cnt2[i];
            else ans+= cnt1[i];
        }
        res+= ans*(1ll<<b);
    }
    cout<<res<<endl;
}

int32_t main() {
    fastio();
    solve();
}

I came across this question from USACO SILVER 2025, being new on cf took me hour(s) to crack it, and when I did, it used a basic property that SUM(abs(a[i]-x)) 1<=i<=n in an array a , is minimum if x is median. Sharing my approach and solution, Open for suggestions on how to improve thought process.

CODE->

#include <bits/stdc++.h>
using namespace std;

#define fastio() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

#define int long long
#define double long double

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define endl '\n'

#define IN_VEC(v,n) vector<int> v(n); for(auto &i : v) cin >> i;
#define IN_ARR(arr,n) for(int i=0;i<n;i++) cin >> arr[i];

const ll INF = 1e18;
const int MOD = 1e9 + 7;
void solve() {
    int n,m;
    cin>>n>>m;
    vector<int> a(n),pref(2*n+1,0);
    for(int i=0;i<n;++i){
    	int y;
        cin>>y;
    	a[i]=y%m;
    }
    sort(all(a));
    for(int i=0;i<n;++i){
        a.pb(a[i]+m);
    }
    for(int i=1;i<=2*n;++i){
        pref[i]=pref[i-1]+a[i-1];
    }
    int ans=INF;
    for(int i=0;i<n;++i){
        // window from i to i+n-1 is sorted and shows unwraping of circle, its median minimizes cost 
        // each cut fixes x%m, there are n distinct cuts, so n distinct x%m that can minimize cost
        // make min cost over them
        // for a fixes cut this is just linear absolute sum --> min at median if sorted, which is!!
        int me=i+n/2;
        int t1=(me-i)*a[me];
        int t2=(pref[me]-pref[i]);
        int t3=(pref[n+i]-pref[me]);
        int t4=(n+i-me)*a[me];
        ans=min(ans,t1+t3-t2-t4);
    }
    cout<<ans<<endl;
}

int32_t main() {
    fastio();
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}