#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], prof[maxn], ja[maxn], n, in[maxn], low[maxn], tmp, lim, da; bool sair; pair<int,int>z[3]; void calc(int u, int c){ //cout << u << " " << cor[u] << endl; if(!lim||cor[u]) return; cor[u]=c; lim--; for(int viz : v[u]) if(in[viz]>=in[u]) calc(viz,c); } void dfs(int u){ if(sair) return; marc[u]++; sub[u]=1; in[u]=low[u]=++tmp; int ma=0; for(int viz : v[u]){ low[u]=min(low[u],in[viz]); if(marc[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]; } if(sub[u]>=z[0].first&&ma<z[0].first){ // achei o cara com a propriedade; int x=sub[u], y=n-sub[u]; for(int viz : v[u]){ if(z[0].first<=y) break; if(in[viz]<in[u]||low[viz]>=in[u]) continue; // ou seja tem backedge para cima in[viz]=0; x-=sub[viz]; y+=sub[viz]; } if(z[0].first<=y){ // deu bom if(z[1].first>y) swap(z[0],z[1]); assert(z[0].first<=x&&z[1].first<=y); lim=z[0].first; calc(u,z[0].second); memset(in,0,sizeof(in)); lim=z[1].first; calc(0,z[1].second); // dando errado aq for(int i=0;i<n;i++) if(!cor[i]) cor[i]=z[2].second; da=true; } sair=true; return; } } vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q){ 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); da=sair=false; dfs(0); vector<int>resp(n,0); for(int i=0;i<n;i++) resp[i]=cor[i]; return resp; }