#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long
using namespace std;
const int N=1e5+5,M=2e3+10,mod=100000000000031;
vector<int>adj[N];
long long summ(long long x,long long y){
return ((x%mod)+(y%mod))%mod;
}
long long mult(long long x,long long y){
return ((x%mod)*(y%mod))%mod;
}
ll dp[N][25],num[N],a[N],ans[N][25],xx[25];
int aa[N][25];
void dfs2(int node,int par){
for(auto x:adj[node]){
if(x==par)
continue;
dfs2(x,node);
}
for(auto x:adj[node])
num[node]+=num[x];
num[node]++;
}
void dfs(int node,int par){
for(auto x:adj[node]){
if(x==par)
continue;
dfs(x,node);
}
for(int j=0;j<=24;j++){
if(aa[node][j]==1){
for(auto x:adj[node]){
if(x==par)
continue;
dp[node][j]+=num[x]-dp[x][j];
}
if(adj[node].size()!=1||node==1)
dp[node][j]++;
}
else
for(auto x:adj[node])
dp[node][j]+=dp[x][j];
}
if(adj[node].size()==1&&node!=1)
for(int j=0;j<=24;j++)
dp[node][j]=aa[node][j];
}
int n;
void dfs3(int node,int par){
if(node!=1){
for(int j=0;j<=24;j++)
xx[j]=ans[par][j];
for(int j=0;j<=24;j++)
if(aa[par][j]==1)
xx[j]-=(num[node]-dp[node][j]);
else
xx[j]-=dp[node][j];
for(int j=0;j<=24;j++){
if(aa[node][j]==1)
ans[node][j]+=(n-num[node])-xx[j];
else
ans[node][j]+=xx[j];
}
for(int j=0;j<=24;j++)
ans[node][j]+=dp[node][j];
}
for(auto x:adj[node]){
if(x==par)
continue;
dfs3(x,node);
}
}
main()
{
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[i]=x;
for(int j=0;j<=24;j++)
if(x&(1<<j))
aa[i][j]=1;
}
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
adj[x].pb(y);
adj[y].pb(x);
}
dfs2(1,0);
dfs(1,0);
for(int j=0;j<=24;j++)
ans[1][j]=dp[1][j];
dfs3(1,0);
int answer=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=24;j++)
if(ans[i][j]==0)
continue;
else
answer+=ans[i][j]*(1<<j);
int sum=0;
for(int i=1;i<=n;i++)
sum+=a[i];
answer-=sum;
answer/=2;
answer+=sum;
cout<<answer<<endl;
return 0;
}
Compilation message
deblo.cpp:7:32: warning: overflow in conversion from 'long int' to 'int' changes value from '100000000000031' to '276447263' [-Woverflow]
7 | const int N=1e5+5,M=2e3+10,mod=100000000000031;
| ^~~~~~~~~~~~~~~
deblo.cpp:122:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
122 | main()
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2660 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
3184 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
3156 KB |
Output isn't correct |
| 6 |
Incorrect |
185 ms |
65536 KB |
Output isn't correct |
| 7 |
Incorrect |
191 ms |
65536 KB |
Output isn't correct |
| 8 |
Incorrect |
200 ms |
59584 KB |
Output isn't correct |
| 9 |
Incorrect |
207 ms |
58964 KB |
Output isn't correct |
| 10 |
Incorrect |
247 ms |
58156 KB |
Output isn't correct |
