Suma de Subarreglos mediante Operaciones XOR

Dado un arreglo de tamaño \(n\), se requiere calcular la suma de todas las sumas XOR para cada subarreglo posible. El problema considera múltiples casos de prueba con diferentes tamaños de entrada.

Análisis de Solución

Optimización por bits: Se utiliza la propiedad de bits independientes para procesar cada componente binario por separado. La técnica aprovecha:

• Precálculo de XOR acumulativo para acceso rápido a rangos
• Conteo dinámico de pares que activan bits específicos

Implementación Eficiente

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int casos;
  cin >> casos;
  
  while (casos--) {
    int tam;
    cin >> tam;
    vector<long> arr(tam);
    for (int i = 0; i < tam; ++i) cin >> arr[i];
    
    vector<long> acum(tam + 1);
    for (int i = 0; i < tam; ++i)
      acum[i + 1] = acum[i] ^ arr[i];
    
    unsigned long long total = 0;
    for (int bit = 0; bit < 31; ++bit) {
      int contarCeros = 1, contarUnos = 0;
      unsigned long sumaParcial = 0;
      
      for (int i = 1; i <= tam; ++i) {
        if (acum[i] >> bit & 1) {
          sumaParcial += contarCeros;
          contarUnos++;
        }
        else {
          sumaParcial += contarUnos;
          contarCeros++;
        }
      }
      total += sumaParcial * (1LL << bit);
    }
    cout << total << '\n';
  }
  
  return 0;
}

Rutas de Longitud Par en Estructuras Arbóreas

Dado un árbol no dirigido, se calcula el número de caminos que contienen exactamente un número par de nodos entre nodos arbitrarios.

Técnica de Resolución

DP en árboles: Se implementa un recorriod DFS que almacena estados según paridad de distancias:

• [0]: Recuento de rutas con distancia par
• [1]: Recuento de rutas con distancia impar

Se actualiza dinámicamente durante recorrido

Solución Óptima

#include <iostraem>
#include <vector>
using namespace std;

int main() {
  int totalNodos;
  cin >> totalNodos;
  vector<vector<int>> conexiones(totalNodos);
  
  for (int i = 1; i < totalNodos; ++i) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    conexiones[u].push_back(v);
    conexiones[v].push_back(u);
  }
  
  vector<vector<int>> estados(totalNodos, vector<int>(2, 0));
  
  function<void(int, int)> dfs = [&](int actual, int padre) {
    for (int hijo : conexiones[actual]) {
      if (hijo == padre) continue;
      dfs(hijo, actual);
      estados[actual][0] += estados[hijo][1];
      estados[actual][1] += estados[hijo][0] + 1;
    }
  };
  
  dfs(0, -1);
  long long resultado = (long long)(estados[0][0] + 1) * estados[0][1];
  cout << resultado;
  
  return 0;
}