Advertisement
BaoJIaoPisu

Untitled

Nov 14th, 2021
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.14 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define pb push_back
  5. #define pf push_front
  6. #define popb pop_back
  7. #define popf pop_front
  8. #define ins insert
  9. #define pq priority_queue
  10. #define minele min_element
  11. #define maxele max_element
  12. #define lb lower_bound //first pos >= val
  13. #define ub upper_bound // first pos > val
  14. #define cnt_bit __builtin_popcount
  15. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  16. using namespace std;
  17.  
  18. typedef unsigned long long ll;
  19. typedef pair<ll, ll> pll;
  20. typedef pair<int, int> pii;
  21.  
  22. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  23. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  24. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  25.  
  26. const ll oo = 1e18;
  27. const ll maxN = 1e6;
  28.  
  29. const int LOG = 30;
  30. const int N = 1e5 + 2710;
  31. vector<pii> g[N];
  32. vector<int> son[N];
  33. int sz[N];
  34. ll cnt[LOG + 5][2];
  35. int child[N];
  36. ll num[N];
  37. ll ans = 0;
  38.  
  39. void dfs_sub1(int u, int par, ll val) {
  40.     ans += val;
  41.     for(pii v : g[u]) {
  42.         if(v.fi != par) {
  43.             dfs_sub1(v.fi, u, val ^ v.se);
  44.         }
  45.     }
  46. }
  47.  
  48. void sub1(int n) {
  49.     for(int i = 1; i < n; i++) {
  50.         int u, v, L;
  51.         cin >> u >> v >> L;
  52.         g[u].pb(make_pair(v, L)); g[v].pb(make_pair(u, L));
  53.     }
  54.    
  55.     for(int i = 1; i <= n; i++) {
  56.         dfs_sub1(i, 0, 0);
  57.     }  
  58.    
  59.     cout << ans / 2;
  60. }
  61.  
  62. void dfssz(int u, int par) {
  63.     sz[u] = 1;
  64.     for(pii v : g[u]) {
  65.         if(v.fi != par) {
  66.             num[v.fi] = num[u] ^ v.se;
  67.             dfssz(v.fi, u);
  68.             sz[u] += sz[v.fi];
  69.         }
  70.     }
  71. }
  72.  
  73. void dfs(int u, int par, bool isBig) {
  74.     int big = 0; ll ed = 0;
  75.     for(pii v : g[u]) {
  76.         if(v.fi != par && sz[v.fi] > sz[big]) big = v.fi, ed = v.se;
  77.     }
  78.    
  79.     for(pii v : g[u]) {
  80.         if(v.fi != par && v.fi != big) dfs(v.fi, u, false);
  81.     }
  82.    
  83.     if(big > 0) {
  84.         dfs(big, u, true);
  85.         swap(son[u], son[big]);
  86.     }  
  87.    
  88.     for(int i = 0; i <= LOG; i++) {
  89.         int p = (ed >> i & 1);
  90.         if(p > 0) swap(cnt[i][0], cnt[i][1]);
  91.         ans += 1ll * (1ll << i) * cnt[i][1];
  92.         ++cnt[i][0];
  93.     }
  94.    
  95.     son[u].pb(u);
  96.    
  97.     for(pii v : g[u]) {
  98.         if(v.fi != par && v.fi != big) {
  99.             int iter = 0;
  100.             for(auto c : son[v.fi]) {
  101.                 ll curr = num[c] ^ num[u];
  102.                 for(int i = 0; i <= LOG; i++) {
  103.                     int p = (curr >> i & 1);
  104.                     ans += 1ll * (1ll << i) * cnt[i][p ^ 1];
  105.                 }
  106.                
  107.                 child[++iter] = c;
  108.             }
  109.            
  110.             for(int i = 1; i <= iter; i++) {
  111.                 son[u].pb(child[i]);
  112.                 ll curr = num[child[i]] ^ num[u];
  113.                 for(int j = 0; j <= LOG; j++) {
  114.                     int p = (curr >> j & 1);
  115.                     ++cnt[j][p];
  116.                 }
  117.             }
  118.         }
  119.     }
  120.    
  121. //  cout << debug(u) debug(ans) << endl;
  122. //  for(int i = 0; i <= 3; i++) {
  123. //      cout << debug(i) debug(cnt[i][0]) debug(cnt[i][1]) << endl;
  124. //  }
  125.    
  126.     if(!isBig) {
  127.         for(int i = 0; i <= LOG; i++) cnt[i][0] = cnt[i][1] = 0;
  128.     }
  129. }
  130.  
  131. void sub3(int n) {
  132.     for(int i = 1; i < n; i++) {
  133.         int u, v, L;
  134.         cin >> u >> v >> L;
  135.         g[u].pb(make_pair(v, L)); g[v].pb(make_pair(u, L));
  136.     }
  137.    
  138.     dfssz(1, 0);
  139.     dfs(1, 0, 1);
  140.     cout << ans;
  141. }
  142.  
  143. void solve() {
  144.     int n; cin >> n;
  145.     if(n <= 3000) {
  146.         sub1(n);
  147.         return;
  148.     }
  149.    
  150.     //DSU ON TREE
  151.     sub3(n);
  152. }
  153.  
  154. int main()
  155. {
  156.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  157.     //freopen("XTREEW.inp", "r", stdin);
  158.     //freopen("XTREEW.out", "w", stdout);
  159.     solve();
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement