F - Strange Memory

/*
 *@author spnooyseed
 */
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair PII ;
const int N = 2e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7 , M = 1e5 + 10;
int a[M] , n ;
vector v[M] ;
int sz[M]  , son[M] , vis[M] ;
ll ans ;

ll h[N][22][2] ;

void dfs_rt(int u , int f) {
  sz[u] = 1 ;
  for(auto x : v[u]) {
    if(x == f) continue ;
    dfs_rt(x , u) ;
    sz[u] += sz[x] ;
    if(!son[u] || sz[son[u]] < sz[x]) son[u] = x ;
  }
}

void add(int u , int keep) {
  int t = a[u] ;
  for(int i = 0 ;i < 20 ;i ++ )
   h[t][i][u % 2] += keep , u /= 2 ;
}
void count(int u , int f , int lca) {
  int t = a[u] ^ a[lca] , m = u ;
  for(int i = 0 ;i < 20 ;i ++ )
   ans += 1ll * h[t][i][1 - m % 2] * (1 << i) , m /= 2 ;
  for(auto x : v[u]) {
    if(x == f) continue ;
    count(x , u , lca) ;
  }
}
void dfs1(int u , int f , int keep) {
   add(u , keep) ;
   for(auto x : v[u]) {
     if(x == f) continue ;
     dfs1(x , u , keep) ;
   }
}
void update(int u , int f , int keep) {
   for(auto x : v[u]) {
     if(x == f || vis[x]) continue ;
     if(keep == 1) count(x , u , u) ;
     dfs1(x , u , keep) ;
   }
   add(u , keep) ;
}
void solve(int u , int f , int keep) {
    for(auto x : v[u]) {
      if(x == f || x == son[u]) continue ;
      solve(x , u , 0) ;
    }
    if(son[u]) solve(son[u] , u , 1) , vis[son[u]] = 1 ;
    //   cout << u << " " << f << " " << keep << endl ;
    // puts("before") ;
    // for(int i = 1; i <= 6 ;i ++ ) {
    //   for(int j = 0 ;j < 4 ;j ++ )
    //    cout << "value = "<< i << " idx = " << j << " idx0 = " << h[i][j][0] << " idx1 = " << h[i][j][1] << endl ;
    // }
    update(u , f , 1) ;
    // cout << u << " " << f << " " << keep << endl ;
    // puts("after") ;
    // for(int i = 1; i <= 6 ;i ++ ) {
    //   for(int j = 0 ;j < 4 ;j ++ )
    //    cout << "value = "<< i << " idx = " << j << " idx0 = " << h[i][j][0] << " idx1 = " << h[i][j][1] << endl ;
    // }
    if(vis[son[u]]) vis[son[u]] = 0 ;
    if(!keep) update(u , f , -1) ;
    //   cout << u << " " << f << " " << keep << endl ;
    // puts("last") ;
    // for(int i = 1; i <= 6 ;i ++ ) {
    //   for(int j = 0 ;j < 4 ;j ++ )
    //    cout << "value = "<< i << " idx = " << j << " idx0 = " << h[i][j][0] << " idx1 = " << h[i][j][1] << endl ;
    // }
}
int work()
{
  scanf("%d" , &n) ;
  for(int i = 1; i <= n ;i ++ ) scanf("%d" , &a[i]) ;
  for(int i = 1; i < n ;i ++ ) {
    int a , b ;
    scanf("%d%d" , &a , &b) ;
    v[a].push_back(b) , v[b].push_back(a) ;
  }

  dfs_rt(1 , 0) ;
  // for(int i = 1; i <= n ;i ++ )
  //  cout << son[i] << " " ;
  // puts("") ;
  solve(1 , 1 , 0) ;
  cout << ans << endl ;
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;

  work() ;
  return 0 ;
}
/*
*/
树上启发式合并CCPC

相关

The 2021 CCPC Guilin Onsite【A,I,G(二分),D（思维+构造）,E（最短路】

《2021CCPC桂林》

2021CCPC广州 C. Necklace（二分/贪心/好题/详细题解）

DSU 树上启发式合并的复杂度 小记

2021CCPC威海H题city safety (最小割模型 or 树形dp）

秦皇岛2020CCPC补题

标签