Stand Hunt

Required Knowledge : Basic Trees, Bit Manipulation

Time Complexity : $O(60 \cdot N)$

Editorialist : TheoGermal

Approach:

Let's start by rooting the tree somewhere, without any loss of generality, let's root it at node $1$ . Now let's try to figure out a more convenient way of representing $F(i, j)$ . Consider the Least Common Ancestor (LCA) of $i, j$ . If you carefully observe the path from node $1$ to $i$ and the path from node $1$ to $j$ , you can see that the path from node $1$ to $lca$ is common in both of these paths while the uncommon part is the actual path from $i$ to $j$ .

This gives us an easy way of representing $F(i, j)$ . We can say $F(i, j) = F(1, i) \oplus F(1, j)$ . The common path gets cancelled out due to the property of xor yielding $0$ when it's done on itself, resulting only values on the simple path from $i$ to $j$ being xorred.

Now when it comes to finding out $\sum_{1 \leq i < j \leq N} F (i, j)$ , it's just $\sum_{1 \leq i < j \leq N} F(1, i) \oplus F(1, j)$ . If we precompute values of $F(1, x)$ for all $1 \leq x \leq N$ , The problem turns out to be Sum of XOR of Pairs which is a well known standard problem solvable by Bit manipulation.

Coming to the asymptotics, precomputing $F(1, x)$ is done using plain dfs in $O(N)$ and solving for Sum of XOR of pairs can be done in $O(60 \cdot N)$ as array values can go up to $2^{60}$ . So the entire complexity becomes $O(60 \cdot N)$

Setter's Code:

// Author : Sreekar Vyas

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using pbds =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// #define cerr if(false)cerr
#define int long long
#define pb push_back
#define F first
#define S second
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define yn(x) x ? yes : no
#define f(i, s, e) for (int i = s; i < e; i++)
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int, int>
#define vpi vector<pii>
#define all(x) x.begin(), x.end()
#define minele(x) *min_element(all(x))
#define maxele(x) *max_element(all(x))
#define endl '\n'
#define in(v, x) binary_search(all(v), x)

const int N = 1 + 2e5;
const int MOD = 1e9 + 7;
const int inf = LLONG_MAX;
const int minf = LLONG_MIN;

#ifndef ONLINE_JUDGE
#define debug(x)            \
    cerr << (#x) << " is "; \
    _print(x)
#define dbg(x...)           \
    cerr << (#x) << " is "; \
    _print(x)
#else
#define debug(x)
#define dbg(x)
#define dbg(x...)
#endif

template <typename T>
void _print(T a) {
    cerr << a;
}
template <typename T1, typename... T2>
void _print(T1 t1, T2... t2) {
    cerr << t1 << ", ";
    _print(t2...);
    cerr << endl;
}
template <typename T>
void print(T a) {
    cout << a << ' ';
}
template <typename T>
void println(T a) {
    cout << a << endl;
}
template <class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &x : a) is >> x;
    return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) {
    for (const auto &x : a) os << x << ' ';
    return os;
}

template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p) {
    cerr << "{";
    _print(p.F);
    cerr << ",";
    _print(p.S);
    cerr << "} ";
}
template <class T>
void _print(vector<T> v) {
    cerr << "[ ";
    for (T i : v) {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T>
void _print(set<T> v) {
    cerr << "[ ";
    for (T i : v) {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T>
void _print(multiset<T> v) {
    cerr << "[ ";
    for (T i : v) {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T, class V>
void _print(map<T, V> v) {
    cerr << "[ ";
    for (auto i : v) {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T, class V>
void _print(unordered_map<T, V> v) {
    cerr << "[ ";
    for (auto i : v) {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void chadd(int &a, int b) {
    a %= MOD;
    b %= MOD;

    a = (a + b) % MOD;
}
int mul(int a, int b) {
    a %= MOD;
    b %= MOD;

    return (a * b) % MOD;
}

vpi Tree[N];
vi till(N);

void dfs(int par, int node) {
    for (auto i : Tree[node]) {
        if (i.F != par) {
            till[i.F] = i.S ^ till[node];
            dfs(node, i.F);
        }
    }
}

void solve() {
    int n;
    cin >> n;

    f(i, 0, n - 1) {
        int s, d, w;
        cin >> s >> d >> w;
        Tree[s].pb({d, w});
        Tree[d].pb({s, w});
    }
    dfs(0, 1);
    vpi bits(63);

    for (int i = 1; i <= n; i++) {
        for (int j = 62; j >= 0; j--) {
            if ((till[i] >> j) & 1) {
                bits[j].F++;
            } else {
                bits[j].S++;
            }
        }
    }

    int ans = 0;
    for (int i = 62; i >= 0; i--) {
        chadd(ans, mul(1LL << i, bits[i].F * bits[i].S));
    }

    cout << ans << endl;
}

signed main() {
    fast();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Editorial for Problem G

Stand Hunt

Approach:

Setter's Code: