#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
#include <utility>
#include<stack>
using namespace std;
#define pb push_back
#define mp make_pair
/// COCI DEBLO 2018 CONTEST 2
/// SKONTO: ZA SVAKI OD 30AK BITOVA, GRADIMO DP NA STABLO.
/// DP[X][Y] SU PUTEVI KOJIMA JE X POCETNI CVOR I IDU PREMA DOLE, ILI JE X PRELOMNICA, TJ.
/// IDE IZ NEKOG DJETETA U DRUGO. Y PREDSTAVLJA SAMO PARNOST.
/// KOMBINUJEMO SAD NE PRETESKO: AKO X IMA FIKSAN TAJ BIT, ONDA UZMEMO ZBIR PARNE DJECE, I JOS
/// PROIZVOD ZBIRA NEPARNE I NEPARNE, KAO I PARNE I PARNE DJECE, JER SU TO SVI MOGUCI
/// PUTEVI KOJI CE ZADOVOLJAVATI.
/// PROBAT OVO IMPLEMENTIRATI
///GRESKA U LOGICI: KAD DODAJEM PUTEVE U NEKI CVOR, DODAM I NEVALIDNE, JER DODAM ONE STO SE GRANAJU NA GORNJI..
/// preispito sam opet, fakat se cini dobro
/// 10 22
/// OPET NEKI PROBLEMI
int n;
long long val[100010];
long long dp[100010][2];
long long res[100010];
long long tot[100010][2];
int par[100010];
vector<vector<int>> adjl;
long long dfs( int x, int p, bool paran, long long bit )
{
// cout << x<< " " <<paran<<" "<<bit<<endl;
if( dp[x][paran]!=-1 ) return dp[x][paran];
/// mozda je problem u ovom -1, mada sumnjam
par[x]=p;
bool type;
if( val[x]&bit ) type=1;
else type=0;
if( adjl[x].size()<=1 ){
if( x==0 ) 1;
else if( type==paran && x!=0 ) return tot[x][paran]=dp[x][paran]=1;
else return tot[x][paran]=dp[x][paran]=0;
}
long long sumap=0,suman=0,sqrp=0,sqrn=0,mix=0;
for( int i=0;i<adjl[x].size();i++ ){
int v=adjl[x][i];
if( v==par[x] ) continue;
long long tmp1=dfs(v,x,0,bit);
sumap+=tmp1;
sqrp+=tmp1*tmp1;
long long tmp2=dfs(v,x,1,bit);
suman+=tmp2;
sqrn+=tmp2*tmp2;
mix+=tmp1*tmp2;
}
// cout << " eto " <<endl;
/// sad tek ide apdejt;
if( type!= paran ){
// if( bit==1 && x==1 ) cout <<suman << " " << mix << " konju " <<endl;
dp[x][paran]=tot[x][paran]=0;
dp[x][paran]+=suman; /// putevi koji pocinjju u x i silaze
tot[x][paran] = dp[x][paran];
tot[x][paran]+=(suman*sumap);
tot[x][paran]-=mix;
// cout <<x << " " << bit << " " << tot[x][paran ] << " karagaa " <<endl;
}
else{
// cout <<x <<" " << bit << " "<< type << " " << paran << " "<< sumap << " " << suman << " " << sqrp << " eee " <<sqrn<<endl;
// if( bit == 4 && x == 2 ) cout << sumap << " " << suman << " lokum " << sqrp <<endl;
dp[x][paran]=tot[x][paran]=1;
dp[x][paran]+=sumap;
tot[x][paran]=dp[x][paran];
long long tmp = ( sumap*sumap - sqrp )/2;
tot[x][paran]+=tmp;
tmp=( suman*suman - sqrn )/2;
tot[x][paran]+=tmp;
}
// if( tot[x][paran] ==-1 ) cout << " koji breee " <<endl;
return dp[x][paran];
}
int main()
{
int u,v;
cin>>n;
adjl.resize(n);
for( int i=0;i<n;i++ ){
cin>>val[i];
dp[i][0]=dp[i][1]=-1;
}
for( int i=0;i<n-1;i++ ){
cin>>u>>v;
u--;
v--;
adjl[u].pb( v );
adjl[v].pb( u );
}
// cout << adjl[3].size() << " debilu " <<endl;
long long res=0;
par[0]=-1;
for( int j=0;j<22;j++ ){
for( int i=0;i<n;i++ ) dp[i][0]=dp[i][1]= tot[i][0]=tot[i][1]=-1;
for(int i=0;i<n;i++){
//cout << j << " " << i << " eto " <<endl;
//dp[i][0]=dp[i][1]=-1;
// long long curr=dfs( i, par[i],1,( 1<<j ) );
if( tot[i][1]!=-1 ) res+=tot[i][1]*( 1<<j );
else {
dfs( i,par[i],1,( 1<<j ) );
/// ovdje ispod bude tot[i] -1 bez razloga, a gore u dfs nikad ne bude. kako ti
// cout << i << " " << (1<<j) << " " << tot[i][1] << " totittt " <<endl;
res+=tot[i][1]*( 1<<j );
}
// res+=dfs( i,par[i],1, (1<<j) )*( (1<<j) );
// cout<<( 1<<j ) << " " << i << " "<< dp[i][0] << " " << dp[i][1] << " glavno " <<curr <<endl;
//if( j==0 ) cout << dp[4][1] << " kiko " <<endl;
}
// for( int i=0;i<n;i++ ) cout<<(1<<j) << " " << i << " " << tot[i][0] << " " << tot[i][1] << " " <<dp[i][1] << " bhal "<<endl;
}
cout<<res<<endl;
return 0;
}
Compilation message
deblo.cpp: In function 'long long int dfs(int, int, bool, long long int)':
deblo.cpp:47:25: warning: statement has no effect [-Wunused-value]
if( x==0 ) 1;
^
deblo.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i=0;i<adjl[x].size();i++ ){
~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
512 KB |
Output is correct |
| 5 |
Correct |
4 ms |
512 KB |
Output is correct |
| 6 |
Correct |
269 ms |
24696 KB |
Output is correct |
| 7 |
Correct |
272 ms |
24440 KB |
Output is correct |
| 8 |
Correct |
249 ms |
14584 KB |
Output is correct |
| 9 |
Correct |
264 ms |
13240 KB |
Output is correct |
| 10 |
Correct |
694 ms |
12024 KB |
Output is correct |
