oj.uz

Submission #703657

# Submission time Handle Problem Language Result Execution time Memory
703657 2023-02-28T03:36:24 Z alanl Deblo (COCI18_deblo) C++14
90 / 90
 136 ms 58624 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
using namespace std;
typedef pair<long long,long long> pll;
typedef pair<int,int> pii;
typedef long long ll;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const vector<A> &p){
	for(const auto &a:p)
		os << a << " ";
	os << "\n";
	return os;
}

ll val[100010], dp[100010][26][2], ans;
vector<int> adj[100010];

void dfs1(int v, int p){
	for(auto a:adj[v]){
		if(a!=p){
			dfs1(a, v);
			rep(i,0,26){
				if(val[v]&(1<<i)) dp[v][i][1]+=dp[a][i][0], dp[v][i][0]+=dp[a][i][1];
				else dp[v][i][1]+=dp[a][i][1], dp[v][i][0]+=dp[a][i][0];
			}
		}
	}
	rep(i,0,26){
		if(val[v]&(1<<i)) dp[v][i][1]++;
		else dp[v][i][0]++;
	}
}

void dfs2(int v, int p){
	rep(i,0,26) ans+=dp[v][i][1]*(1ll<<i);
	for(auto a:adj[v]){
		if(a!=p){
			rep(i,0,26){
				ll t1=dp[v][i][1], t0=dp[v][i][0];
				if(val[v]&(1<<i)) t1-=dp[a][i][0], t0-=dp[a][i][1];
				else t1-=dp[a][i][1], t0-=dp[a][i][0];
				if(val[a]&(1<<i)) dp[a][i][1]+=t0, dp[a][i][0]+=t1;
				else dp[a][i][1]+=t1, dp[a][i][0]+=t0;
			}
			dfs2(a, v);
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	ll sum=0;
	rep(i,1,n+1) cin>>val[i], sum+=val[i];
	rep(i,0,n-1){
		int a, b;
		cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	dfs1(1, 0);
	dfs2(1, 0);
	cout<<(ans-sum)/2+sum<<NL;
}

Subtask #1
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 3 ms 3084 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 112 ms 58624 KB Output is correct
7 Correct 109 ms 58500 KB Output is correct
8 Correct 135 ms 50784 KB Output is correct
9 Correct 118 ms 50024 KB Output is correct
10 Correct 136 ms 49208 KB Output is correct