#include "split.h" #include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; vector<int>v[maxn], filhos[maxn]; int marc[maxn], sub[maxn], pai[maxn], cor[maxn], val[maxn], prof[maxn], ja[maxn], n; bool sair; pair<int,int>z[3]; int calc(int u, int x, int c, int lim){ ja[u]++; if(x){ //cout << "! " << x << " " << u << ' ' << c << endl; cor[u]=c; x--; } for(int viz : v[u]){ if(ja[viz]||prof[viz]<lim) continue; x=calc(viz,x,c,lim); } return x; } int termina(int u, int x, int c){ ja[u]++; if(x){ //cout << "! " << x << " " << cor[u] << " " << u << " " << c << endl; cor[u]=c; x--; } for(int viz : v[u]){ if(ja[viz]||cor[viz]) continue; x=termina(viz,x,c); } return x; } void dfs(int u){ marc[u]++; sub[u]=1; int ma=0; for(int viz : v[u]){ if(pai[u]==viz) continue; if(marc[viz]){ if(prof[viz]<prof[u]){ // marcando as backedges val[u]++; val[viz]--; } continue; } filhos[u].push_back(viz); pai[viz]=u; prof[viz]=prof[u]+1; dfs(viz); if(sair) return; ma=max(ma,sub[viz]); sub[u]+=sub[viz]; val[u]+=val[viz]; } if(sub[u]>=z[0].first&&ma<z[0].first){ // achei o cara com a propriedade // cout << "get " << u << " " << pai[u] << endl; int x=sub[u], y=n-sub[u]; vector<int>aux; for(int viz : filhos[u]){ if(val[viz]){ // ou seja tem backedge para cima if(x-sub[viz]>=z[0].first){ aux.push_back(viz); x-=sub[viz]; }else{ // deu bom já for(int viz : aux) z[1].first=calc(viz,z[1].first,z[1].second,prof[viz]); for(int viz : v[u]) if(!ja[viz]&&viz!=pai[u]) z[0].first=calc(viz,z[0].first,z[0].second,prof[viz]); if(z[0].first){ cor[u]=z[0].second; z[0].first--; } z[1].first=termina(pai[u],z[1].first,z[1].second); sair=true; return; } } } } } vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q){ int n=N; for(int i=0;i<p.size();i++){ v[p[i]].push_back(q[i]); v[q[i]].push_back(p[i]); } z[0]={a,1}; z[1]={b,2}; z[2]={c,3}; sort(z,z+3); sair=false; //cout << z[0].first << " " << z[1].first << " " << z[2].first << endl; dfs(1); //cout << z[0].first << " " << z[1].first << " " << z[2].first << endl; vector<int>resp(n,0); for(int i=0;i<n;i++){ //cout << cor[i] << ' '; if(cor[i]) resp[i]=cor[i]; else resp[i]=z[2].second; } //cout << endl; return resp; }