Submission #200086

#	Time	Username	Problem	Language	Result	Execution time	Memory
200086		Saboon	Deblo (COCI18_deblo)	C++14	90 / 90	348 ms	18296 KiB

deblo

#include <bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10;
int l[maxn], r[maxn], u[maxn], d[maxn];

vector <int> v[maxn];
int a[maxn];

int ted[maxn][2];

ll ans;

void dfs (int u, int bit, int par = -1) {
	bool p = (a[u] >> bit) & 1;
	ted[u][p] = 0;
	ted[u][1 - p] = 0;
	for (auto w : v[u]) {
		if (w != par) {
			dfs (w, bit, u);
			ted[u][0] += ted[w][0];
			ted[u][1] += ted[w][1];
		}
	}
	
	if (p) {
		ll tmp = 0;
		for (auto w : v[u]) {
			if (w != par) {
				tmp += (1ll << bit) * ted[w][0] * (ted[u][0] - ted[w][0]);
				tmp += (1ll << bit) * ted[w][1] * (ted[u][1] - ted[w][1]);
			}
		}
		ans += tmp / 2;
		ans += (ted[u][0] + 1) * (1ll << bit);
		tmp = ted[u][0];
		ted[u][0] = ted[u][1];
		ted[u][1] = tmp + 1;
	}
	else {
		ll tmp = 0;
		for (auto w : v[u]) {
			if (w != par) {
				tmp += (1ll << bit) * ted[w][0] * (ted[u][1] - ted[w][1]);
				tmp += (1ll << bit) * ted[w][1] * (ted[u][0] - ted[w][0]);
			}
		}
		ans += tmp / 2;
		ans += ted[u][1] * (1ll << bit);
		ted[u][0] ++;
	}
}

int main(){ 
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n - 1; i++) {
		int u, w;
		cin >> u >> w;
		v[u].PB (w);
		v[w].PB (u);
	}
	for (int i = 0; i < 23; i++) {
		dfs (1, i);
	}
	cout << ans << endl;
}

• Subtask 1: 90 / 90