제출 #1284898

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284898		vache_kocharyan	Deblo (COCI18_deblo)	C++20	45 / 90	1098 ms	31332 KiB

deblo

#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();
	long long 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;
}

• Subtask 1: 45 / 90