#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> #include <random> #include <chrono> #include <unordered_set> using namespace std; typedef long long ll; #define UNIQUE_SORT(vec) do { \ sort((vec).begin(), (vec).end()); \ (vec).erase(unique((vec).begin(), (vec).end()), (vec).end()); \ } while(0) #define yes cout << "YES" << endl #define no cout << "NO" << endl #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define LB(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define UB(c, x) distance((c).begin(), upper_bound(all(c), (x))) #define ss second #define ff first #define all(X) X.begin(), X.end() #define rall(X) X.rbegin(), X.rend() #define cinall(X) for(auto &i:X)cin >> i #define printall(X) for(auto &i:X)cout << i const int N = 2e5 + 5; const int LOG = 20; long long v[N], xxor[N][LOG], up[N][LOG], pref[N]; vector<int>G[N]; int depth[N]; int n; void dfs(int node, int parent) { for (auto i : G[node]) { if (i == parent)continue; up[i][0] = node; for (int j = 1; j < LOG; j++) { up[i][j] = up[up[i][j - 1]][j - 1]; } depth[i] = depth[node] + 1; pref[i] = pref[node] ^ v[i]; dfs(i, node); } } int up_k(int a, int k) { for (int i = 0; i < LOG; i++) { if (k & (1 << i)) { a = up[a][i]; } } return a; } int lca(int a, int b) { if (depth[a] > depth[b]) swap(a, b); int delta = depth[b] - depth[a]; b = up_k(b, delta); if (a == b)return a; for (int i = LOG - 1; i >= 0; i--) { if (up[a][i] != up[b][i]) { a = up[a][i]; b = up[b][i]; } } return up[a][0]; } void debug() { for (int i = 1; i <= n; i++) { for (int j = 0; j < 2; j++) { cout << "up [" << i << "]" << "[" << j << "] = " << up[i][j] << endl; } } } void solve() { cin >> n; for (int i = 1; i <= n; i++) { cin >> v[i]; } for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; long long c = v[a] ^ v[b]; G[a].push_back(b); G[b].push_back(a); } pref[1] = v[1]; dfs(1, 0); //debug(); int answ = 0; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { long long x = pref[i]; x ^= pref[j]; x ^= v[lca(i, j)]; answ += x; } } cout << answ; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) { solve(); cout << endl; } return 0; }