#include "split.h" #include<bits/stdc++.h> using namespace std; typedef pair<int, int> ii; typedef vector<int> vi; #define FOR(i,n) for(int i=0;i<n;i++) #define FORi(i,b,n) for(int i=b;i<n;i++) #define FOA(i,n) for(auto i : n) #define len(a) ((int)a.size()) vector<vi> adj; int ssub[1000000]; vi ans; vi par; int dfs(int s, int p=-1){ par[s] = p; ssub[s] = 1; for(auto v : adj[s]) if(v!=p) ssub[s]+=dfs(v, s); return ssub[s]; } int acnt=0; int A; void traveA(int s, int p=-1){ cout<<s<<" "<<p<<endl; cout<<ans[s]<<endl; //cout<<s<<" "<<p<<endl; ans[s] = 1; //cout<<s<<" "<<p<<endl; acnt++; //cout<<s<<" "<<p<<endl; //cout<<adj[s].size()<<endl; for(auto v : adj[s]) if(v!=p) traveA(v, s); if(acnt>A) acnt--, ans[s] = 3; } int bcnt=0; int B; void traveB(int s, int p=-1){ cout<<s<<" "<<p<<endl; cout<<ans[s]<<endl; if(!ans[s]){ ans[s] = 2; bcnt++; } for(auto v : adj[s]) if(v!=p) traveB(v, s); if(bcnt>B && ans[s]==2) bcnt--, ans[s] = 3; } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { A = a; B = b; adj.assign(n+1, vi()); ans.resize(n); par.resize(n+1); FOR(i,len(p)){ adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } dfs(1); int mindiffpos=0, mindiff=1000000000; FOR(i,n){ if(ssub[i+1]>a && ssub[i+1]<mindiff) mindiff = ssub[i+1], mindiffpos = i+1; } cout<<mindiff<<" "<<mindiffpos<<endl; traveA(mindiffpos, par[mindiffpos]); traveB(1); FOR(i,n){ if(ans[i]==2) b--; else if(ans[i]==1) a--; else c--; cout<<ans[i]<<" "; } cout<<endl; cout<<a<<" "<<b<<" "<<c<<endl; if(a || b || c){ ans.assign(n, 0); } return ans; }