monthly-2012/runda-4/solutii

Infoarena Monthly 2012 - Runda 4 - Solutii

==include(page="monthly-2012/runda-4/solutii/prodiv")==

==include(page="monthly-2012/runda-4/solutii/arbore5")==
Arbore5
Alegem radacina arborelui in nodul 1 deoarece nu este important.
Observam ca un query (nod1, nod2) este echivalent cu query-urile (1, nod1) (2, nod2).
Tinem un vector state[nod], initial pe zero si de fiecare data cand intalnim querry(1, nod) facem state[nod] ^=1.
Observam ca pentru fiecare x cu state[x] = 1 daca putem afla culoarea muchiei de la x la father de x, este echivalent cu a adauga sau nu 1 la solutie si a face state[father[x]] ^= 1
Asadar vom face o parcurgere dfs incepand cu nodul 1 astfel:
void dfs(int x){
  vis[x] = 1;
  stack.push_back(x);
 
  for(int i = 0; i < graph[x].size(); ++i)
    if(!vis[graph[x][i]])
      dfs(graph[x][i]);
 
  stack.pop_back();
 
  if(!stack.empty())
    if(state[x] == 1){
      ++sol;
      state[stack.back()] ^= 1;
    }
 
}

==include(page="monthly-2012/runda-4/solutii/arbore5")==