Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <climits>
- #include <set>
- using namespace std;
- vector <int> sas [100005];
- vector <int> synowie[100005];
- bool odw[100005];
- int father[100005];
- int nim_baz[100005];
- int spr_mexow[100005];
- int spr_mexow2[100005];
- int spr_mexow3[100005];
- int nim[100005];
- int temp_nim[100005];
- int ost_nim[100005];
- int mexy_drzew[100005];
- set <int> unikalne_wart_synow[100005];
- int prefix_xor[100005];
- int sufiks_xor[100005];
- int global_n = 0;
- int wyw_make_temp = 0;
- void zeruj_odw()
- {
- for(int i=1; i<=global_n; i++)
- odw[i] = 0;
- }
- void DFS_make_tree(int i)
- {
- odw[i] = 1;
- int ile_sas = sas[i].size();
- for(int j=0; j<ile_sas; j++)
- if(!odw[sas[i][j]])
- {
- father[sas[i][j]] = i;
- synowie[i].push_back(sas[i][j]);
- DFS_make_tree(sas[i][j]);
- }
- }
- void DFS_nim_baz(int i)
- {
- odw[i] = 1;
- int ile_synow = synowie[i].size();
- if(ile_synow==0)
- {
- nim_baz[i] = 0; ///POZYCJA PRZEGRYWAJACA
- return;
- }
- else
- {
- for(int j=0; j<ile_synow; j++)
- DFS_nim_baz(synowie[i][j]);
- nim_baz[i] = 0;
- ///DLA KAZDEGO SYNA
- for(int j=0; j<ile_synow; j++)
- {
- ///ZAZNACZAM W TABLICY SPR_MEXOW INDEKS I
- if(spr_mexow[nim_baz[synowie[i][j]]] == i)
- spr_mexow[nim_baz[synowie[i][j]]] = i+1000000;
- else if(spr_mexow[nim_baz[synowie[i][j]]] != i+1000000)
- spr_mexow[nim_baz[synowie[i][j]]] = i;
- }
- /* if(father[i] != i)
- {
- if(spr_mexow[nim_baz[father[i]]] == i)
- spr_mexow[nim_baz[father[i]]] = i+1000000;
- else if(spr_mexow[nim_baz[father[i]]] != i+1000000)
- spr_mexow[nim_baz[nim_baz[father[i]]]] = i;
- }*/
- for(int j=0; j<=100000; j++)
- {
- if(spr_mexow[j] == i)
- {//cout<<"DODANIE UNIKALNEJ WARTOSCI: "<<j<<"dla: "<<i<<endl;
- unikalne_wart_synow[i].insert(j);}
- if(spr_mexow[j] != i && spr_mexow[j] != i+1000000)
- {nim_baz[i] = j; return; }
- }
- }
- }
- void make_temp(int ja, int nieleg_syn)
- {
- int nim_syna = temp_nim[nieleg_syn];
- int nim_ojca = temp_nim[ja];
- ///JEZLI NIM SYNA JEST 1) MNIEJSZY OD NIM OJCA, 2) JEST UNIKALNY, TO NOWY NIM OJCA = NIM SYNA
- if(unikalne_wart_synow[ja].count(nim_syna) && (father[ja] == ja || temp_nim[father[ja]] != nim_syna))
- temp_nim[ja] = nim_syna;
- }
- void DFS_nim(int i)
- {
- // cout<<"WYWOLANO DSF_NIM: "<<i<<endl;
- odw[i] = 1;
- int ile_synow = synowie[i].size();
- if(father[i]==i)
- ost_nim[i] = nim_baz[i];
- else
- {
- ///na bazie temp_nim ojca i synow tworze wlasny ost_nim
- ///JA JESTEM NOWYM KORZENIEM czyt. zmienia sie orien. miedzy ojcem a mna
- ///musze policzyc nowy temp dla ojca
- make_temp(father[i], i);
- spr_mexow2[temp_nim[father[i]]] = i;
- for(int j=0; j<ile_synow; j++)
- spr_mexow2[temp_nim[synowie[i][j]]] = i;
- for(int j=0; j<=100000; j++)
- if(spr_mexow2[j] != i)
- {ost_nim[i] = j; j=100000+5;}
- }
- for(int j=0; j<ile_synow; j++)
- DFS_nim(synowie[i][j]);
- temp_nim[i] = nim_baz[i];
- //temp_nim[father[i]] = nim_baz[father[i]];
- // cout<<"WYCHODZE Z DFS_NIM: "<<i<<"WYNIK OST: "<<ost_nim[i]<<endl;
- // cout<<endl;
- }
- void DFS_mex(int i, int gdzie_mex)
- {
- odw[i] = 1;
- int ile_synow = synowie[i].size();
- for(int j=0; j<ile_synow; j++)
- {
- spr_mexow3[ost_nim[synowie[i][j]]] = gdzie_mex;
- DFS_mex(synowie[i][j], gdzie_mex);
- }
- }
- int make_mexy_drzew(int i)
- {
- mexy_drzew[i] = ost_nim[i];
- spr_mexow3[ost_nim[i]] = i;
- ///PUSZCZAM DFS PO DRZEWIE I XOROJE MEXY DRZEW I
- DFS_mex(i, i);
- for(int j=0; j<=100000; j++)
- if(spr_mexow3[j] != i)
- {mexy_drzew[i] = j; j=100000+5;}
- return mexy_drzew[i];
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int k;
- int n;
- cin>>k;
- int a;
- int b;
- for(int i=1; i<=k; i++)
- {
- cin>>n;
- for(int j=1; j<=n-1; j++)
- {
- cin>>a;
- cin>>b;
- sas[global_n+a].push_back(global_n+b);
- sas[global_n+b].push_back(global_n+a);
- }
- global_n+=n;
- }
- // cout<<global_n<<endl;
- ///STWORZ DRZEWA
- for(int i=1; i<=global_n; i++)
- if(!odw[i])
- {
- father[i] = i;
- DFS_make_tree(i);
- }
- // for(int i=1; i<=global_n; i++)
- // cout<<"i: "<<i<<" father: "<<father[i]<<endl;
- zeruj_odw();
- for(int i=1; i<=global_n; i++)
- if(!odw[i])
- DFS_nim_baz(i);
- // for(int i=1; i<=global_n; i++)
- // cout<<"i: "<<i<<" nim_baz: "<<nim_baz[i]<<endl;
- // cout<<endl;
- // cout<<endl;
- ///DOTAD OK
- zeruj_odw();
- for(int i=0; i<=100005; i++)
- spr_mexow[i] = 0;
- for(int i=1; i<=global_n; i++)
- temp_nim[i] = nim_baz[i];
- for(int i=1; i<=global_n; i++)
- if(!odw[i])
- DFS_nim(i);
- //for(int i=1; i<=global_n; i++)
- // cout<<"i: "<<i<<" ost_nim: "<<ost_nim[i]<<endl;
- // return 0;
- ///DOTAD OK, KORZYSTAMY TERAZ TYLKO Z OST_NIM JAKO ZBIORU NIM SUM
- /// DLA KAZDEGO WIERZCHOLKA KTORY JEST KORZENIEM W TABLICY "MEXY" DAJEMY MEXA Z DRZEWA
- ///DLA WIERZCHOLKOW NIE-KORZENI ZAPISUJE 0 - NIE ZMIENI TO WYNIKU XORA
- zeruj_odw();
- vector<pair<int, int>> mexy; ///mexy kolejnych drzew i numery ich korzeni
- for(int i=1; i<=global_n; i++)
- if(!odw[i])
- mexy.push_back(make_pair(make_mexy_drzew(i), i));
- int xor_ = 0;
- for(int i=0; i<mexy.size(); i++)
- xor_ = xor_ ^ mexy[i].first;
- if(xor_ == 0)
- {cout<<0; return 0;}
- int result = 0;
- mexy.push_back(make_pair(0,global_n+1)); ///potrzebne by poznac koniec realnie ostatinego drzewa
- ///DLA KAZDEGO DRZEWA
- for(int i=0; i<mexy.size()-1; i++)
- {
- xor_ = xor_ ^ mexy[i].first;
- for(int j=mexy[i].second; j<mexy[i+1].second; j++)
- {
- if(!(xor_ ^ ost_nim[j]))
- result++;
- }
- xor_ = xor_ ^ mexy[i].first;
- }
- cout<<result;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement