#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N, in, iix, lcn[303030], deg[303030];
vector<int> fir[303030], leaf[303030], tree[303030], ins;
vector<pair<int,int> > con[303030], inv[303030]; int concn, invcn;
void edge(vector<pair<int,int> > *v, int s, int e, int &ecn){
v[s].push_back(make_pair(e,ecn));
v[e].push_back(make_pair(s,ecn));
ecn++;
}
void divide(){
for(int i=1; i<=N; i++){
if(deg[i] > N-1-deg[i]) iix=i;
if(deg[i] > 1){
in++, ins.push_back(i);
for(int j=fir[i].size(); j--;){
int e=fir[i][j];
if(deg[e]==1) leaf[i].push_back(e), lcn[i]++;
else tree[i].push_back(e);
}
}
}
}
int tmp[303030], dap;
vector<int> bw[2];
void eachin(int s, int e) { edge(inv, s, e, invcn), deg[s]--, deg[e]--, dap++; }
void dfs1(int s, int ix, int col){
tmp[ix]=1;
if(ix!=s) bw[col].push_back(ix);
for(int i=tree[ix].size(); i--;){
int e=tree[ix][i];
if(!tmp[e]) dfs1(s, e, col^1);
}
}
void color_tree(int s){
if(s == -1){
dfs1(-1, ins[0], 0);
if(bw[0].size() <= 2){
int sz = bw[0].size();
for(int i=0; i<sz-1; i++) eachin(bw[0][i], bw[0][i+1]);
sz = bw[1].size();
for(int i=0; i<sz; i++) eachin(bw[1][i], bw[1][(i+1)%sz]);
}
else{
int sz = bw[1].size();
for(int i=0; i<sz-1; i++) eachin(bw[1][i], bw[1][i+1]);
sz = bw[0].size();
for(int i=0; i<sz; i++) eachin(bw[0][i], bw[0][(i+1)%sz]);
}
return;
}
int left=in-1;
for(int i=tree[s].size(); i--;) tmp[tree[s][i]] = 1;
for(int i=0; i<in; i++){
int e=ins[i];
if(tmp[e]==0 && s!=e) eachin(s, e), left--;
tmp[e]=0;
}
if(left >= 3){
int sz=tree[s].size();
for(int i=0; i<sz; i++){
int a=tree[s][i], b=tree[s][(i+1)%sz];
eachin(a, b);
}
return;
}
dfs1(s, s, 1);
if(left == 1){
if(bw[0].size() >= 2) eachin(bw[0][0], bw[0][1]);
else eachin(bw[1][0], bw[1][1]);
}
else{
eachin(bw[0][0], bw[0][1]);
if(bw[0].size() >= 3) eachin(bw[0][0], bw[0][2]);
else eachin(bw[1][0], bw[1][1]);
}
}
vector<int> lin;
void dfs2(int ix){
tmp[ix]=1;
lin.push_back(ix);
for(int i=tree[ix].size(); i--;){
int e=tree[ix][i];
if(!tmp[e]) dfs2(e);
}
}
void line_tree(int s){
dfs2(s);
int sz=lin.size();
eachin(lin[0], lin[sz-1]);
for(int i=0; i<sz-2; i+=2) eachin(lin[i], lin[i+2]);
for(int i=1; i<sz-2; i+=2) eachin(lin[i], lin[i+2]);
}
struct my {
int sum, ix;
my(int sum_=0, int ix_=0){ sum=sum_, ix=ix_; }
bool operator< (const my &c) const {
return sum < c.sum;
}
};
priority_queue<my> ld, l0, d0;
void push(int s){
my m(lcn[s]+deg[s], s);
if(lcn[s]>0 && deg[s]>0) ld.push(m);
if(lcn[s]==0 && deg[s]>0) l0.push(m);
if(lcn[s]>0 && deg[s]==0) d0.push(m);
}
void eachmatch(int d, int l){
deg[d]--, lcn[l]--;
edge(inv, d, leaf[l][lcn[l]], invcn); dap++;
}
void match(){
for(int i=0; i<in; i++) push(ins[i]);
while(!ld.empty()){
my s=ld.top(), e;
ld.pop();
if(!ld.empty()) e=ld.top(), ld.pop();
else if(!d0.empty()) e=d0.top(), d0.pop();
else e=l0.top(), l0.pop(), swap(s, e);
eachmatch(s.ix, e.ix);
push(s.ix); push(e.ix);
}
while(!l0.empty()){
my s=l0.top(); l0.pop();
my e=d0.top(); d0.pop();
eachmatch(s.ix, e.ix);
push(s.ix); push(e.ix);
}
}
void debug(){
puts("Inner Nodes");
for(int i=0; i<in; i++){
int s=ins[i];
printf("%d: ", s);
for(int j=leaf[s].size(); j--;) printf("%d ", leaf[s][j]);
puts("");
}
puts("Edge");
for(int i=1; i<=N; i++){
for(int j=con[i].size(); j--;) if(i<con[i][j].first) printf("%d-%d\n", i, con[i][j].first);
}
puts("Anti-Edge");
for(int i=1; i<=N; i++){
for(int j=inv[i].size(); j--;) if(i<inv[i][j].first) printf("%d-%d\n", i, inv[i][j].first);
}
}
int cjs[303030], ijs[303030];
int cchk[303030], ichk[303030];
void get_euler(int s, int typ){
if(typ){
while(cjs[s] < con[s].size()){
pair<int,int> im=con[s][cjs[s]++];
int e=im.first, eix=im.second;
if(cchk[eix]) continue;
cchk[eix]=1;
get_euler(e, typ^1);
}
}
else{
while(ijs[s] < inv[s].size()){
pair<int,int> im=inv[s][ijs[s]++];
int e=im.first, eix=im.second;
if(ichk[eix]) continue;
ichk[eix]=1;
get_euler(e, typ^1);
}
}
// printf("%d ", s);
}
int main(){
scanf("%d", &N);
for(int i=0; i<N-1; i++){
int s, e;
scanf("%d%d", &s, &e);
fir[s].push_back(e), fir[e].push_back(s);
deg[s]++, deg[e]++;
}
divide();
if(in <= 1){ puts("0"); return 0; }
if(in == 2){
int a=ins[0], b=ins[1];
int mi = min(lcn[a],lcn[b]);
lcn[a]=lcn[b]=deg[a]=deg[b]=mi;
for(int i=0; i<mi; i++){
edge(con, a, leaf[a][i], concn);
edge(con, b, leaf[b][i], concn);
}
}
else if(in == 3){
if(iix){
int oth = N-1-deg[iix];
lcn[iix]=oth+1-tree[iix].size(), deg[iix]=oth+1;
}
int a=-1, b=-1, c=-1;
iix = ins[0];
for(int i=0; i<3; i++){
if(deg[iix] < deg[ins[i]]) iix=ins[i];
if(tree[ins[i]].size() == 2) b=ins[i];
else if(a<0) a=ins[i];
else c=ins[i];
}
for(int j=0; j<lcn[a]; j++) edge(con, a, leaf[a][j], concn);
for(int j=0; j<lcn[b]; j++) edge(con, b, leaf[b][j], concn);
for(int j=0; j<lcn[c]; j++) edge(con, c, leaf[c][j], concn);
eachin(a, c);
if(iix==a || iix==b){
deg[a]--, deg[b]--;
edge(con, b, c, concn);
}
if(iix==c){
deg[c]--, deg[b]--;
edge(con, b, a, concn);
}
}
else{
if(iix){
int oth = N-1-deg[iix];
lcn[iix]=oth-tree[iix].size(), deg[iix]=oth;
}
for(int i=0; i<in; i++){
int s=ins[i];
for(int j=0; j<lcn[s]; j++) edge(con, s, leaf[s][j], concn);
for(int j=tree[s].size(); j--;){
if(s < tree[s][j]) edge(con, s, tree[s][j], concn);
}
}
if(in == 4){
for(int i=0; i<in; i++){
int s=ins[i];
for(int j=tree[s].size(); j--;) tmp[tree[s][j]] = 1;
for(int j=i+1; j<in; j++){
if(tmp[ins[j]]==0) eachin(s, ins[j]);
}
for(int j=tree[s].size(); j--;) tmp[tree[s][j]] = 0;
}
}
else{
int lsum=0, ovc=0, ovi;
for(int i=0; i<in; i++) lsum += lcn[ins[i]];
for(int i=0; i<in; i++){
int s=ins[i];
if(deg[s]+lcn[s] > lsum) ovc++, ovi=s;
}
if(ovc==0) color_tree(-1);
else if(ovc==1) color_tree(ovi);
else line_tree(ovi);
}
}
match();
// debug();
printf("%d\n", dap*2);
get_euler(ins[0], 1);
return 0;
}
Compilation message
island.cpp: In function 'void get_euler(int, int)':
island.cpp:168:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(cjs[s] < con[s].size()){
~~~~~~~^~~~~~~~~~~~~~~
island.cpp:177:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ijs[s] < inv[s].size()){
~~~~~~~^~~~~~~~~~~~~~~
island.cpp: In function 'int main()':
island.cpp:189:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
island.cpp:192:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &s, &e);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
35832 KB |
Correct |
| 2 |
Correct |
33 ms |
35940 KB |
Correct |
| 3 |
Incorrect |
33 ms |
36148 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
35832 KB |
Correct |
| 2 |
Correct |
33 ms |
35940 KB |
Correct |
| 3 |
Incorrect |
33 ms |
36148 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
