Submission #169521

#TimeUsernameProblemLanguageResultExecution timeMemory
169521Mamnoon_SiamDeblo (COCI18_deblo)C++17
90 / 90
337 ms17156 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ii = pair<int, int>; const int maxn = 1e5 + 5; int n, a[maxn]; vector<int> g[maxn]; int dp[maxn][2]; int val[maxn]; ll contrib = 0; void dfs(int u = 1, int dad = -1) { for(int v : g[u]) if(v ^ dad) { dfs(v, u); } dp[u][0] = dp[u][1] = 0; dp[u][val[u]] = 1; contrib += val[u]; for(int v : g[u]) if(v ^ dad) { for(int t = 0; t < 2; t++) { contrib += dp[v][t ^ 1] * dp[u][t]; dp[u][t] += dp[v][t ^ val[u]]; } } } int main(int argc, char const *argv[]) { #ifdef LOCAL freopen("in", "r", stdin); #endif cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; } for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].emplace_back(v); g[v].emplace_back(u); } ll ans = 0; for(int i = 0; i < 22; i++) { for(int j = 1; j <= n; j++) { if(a[j] & (1 << i)) { val[j] = 1; } else { val[j] = 0; } } contrib = 0; dfs(); ans += contrib * (1LL << i); } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...