UOJ496 新年的新航线
Orz rushcheyo 当场AC
题解
对于n=3的情况显而易见无解。
对于n=4或n=5的情况，图必有一个点直接连接其它所有点，可以直接得到一个菊花子图。
对于n更大的情况，可以通过一些方式来缩小这个图。
如果有解，容易发现每个点度至少为1。
下面所有的+都是循环意义下。命题 对于一个n边形(\(n\geq 4\))的三角剖分，必存在一个点x使得x到x+3有边或x到x+4有边。
证明：
n=4或5显然。
考虑每次取一个最外层的三角形并把它切下来，会增加一条新边。
在还没有出现x到x+3的边或x到x+4的边的情况下，
如果另两条边都是切完新增的边，那么会切出一条x到x+4的边。
如果另两条边有恰好一条是切完新增的边，那么会切出一条x到x+3的边。
所以每次切三角形一定两条边都是原来的边，会减少两条边和一个点。
\(\lfloor \frac{n}{2}\rfloor \geq n-3\)，在\(n\leq 6\)时成立。
对于\(n=6\)的情况最后会得到一个由切下来的边构成的三角形，易知最后一次切的三角形可以当作切另一个三角形从而得到x到x+4的边
对于\(n\gt 6\)时边数不够，无法最后得到一个三角形。
所以成立。
对于\(n\ge 5\)的情况下，每次在剩余的图上重新编号。
找一条x到x+3的边，那么x,x+1,x+2,x+3这四个点会得到一个四边形，如果是x到x+2有边，那么生成树中x到x+1,x+2连一条边，否则x+3到x+1,x+2连边，最后删掉x+1和x+2。
或者找一条x到x+4的边，如果x到x+3,x+1到x+4没边，那么显然x+2到x,x+4都有边。此时生成树中加上x+1,x+2和x+2,x+3两条边，删掉x+1和x+3两个点。
每次删点，其它点要么度数不变，要么+2。易知剩下的图生成树上每个点度数>1，所以度数+2不会使得剩下图中可行方案变为不可行。于是图的规模会-2，归纳可得一定有解。
那么复杂度在于如何找到一个x。
考虑把所有点按顺序串成一个循环链表，在链表上遍历，找到满足条件的x后，加好边，删好点之后x向前跳3次，继续遍历。
由于找到x后，x+1对应的点会变，而(x-1)+1对应的点不会变。于是(x-4)+3,(x-4)+4都不会变。而(x-3)+4会变。
这样起始每个点最多会被遍历一次，而每次找到符合条件的x会有4个点可能多遍历一次，总共遍历复杂度为O(n)，用set判断边是否存在，复杂度为\(O(n\log n)\)，如果用哈希表复杂度为\(O(n)\)。
//实际测试中set吊打tr1::unordered_set
set<int> e[500005];
int l[500005],r[500005];
void del(int x){
x[l][r]=x[r];
x[r][l]=x[l];
}
void work3(int &at){
if(e[at].count(at[r][r])){
write(at,' ',at[r],'\n');
write(at,' ',at[r][r],'\n');
}
else{
write(at[r][r][r],' ',at[r],'\n');
write(at[r][r][r],' ',at[r][r],'\n');
}
del(at[r][r]);
del(at[r]);
at=at[l][l][l];
}
void work4(int &at){
write(at[r][r],' ',at[r],'\n');
write(at[r][r],' ',at[r][r][r],'\n');
del(at[r][r][r]);
del(at[r]);
at=at[l][l][l];
}
signed main(){
#ifdef QAQAutoMaton
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
#endif
int n,u,v;
read(n);
if(n==3)return write("-1\n");
for(int i=1;i<=n-3;++i){
read(u,v);
e[u].insert(v);
e[v].insert(u);
}
for(int i=1;i<=n;++i){
r[i]=(i%n)+1;
l[(i%n)+1]=i;
}
int at=1;
while(n>5){
while(1){
if(e[at].count(at[r][r][r])){
work3(at);
break;
}
if(e[at[r]].count(at[r][r][r][r])){
at=at[r];
work3(at);
break;
}
if(e[at].count(at[r][r][r][r])){
work4(at);
break;
}
at=at[r];
}
n-=2;
}
if(n==4){
while(!e[at].count(at[r][r]))at=at[r];
write(at,' ',at[r],'\n');
write(at,' ',at[r][r],'\n');
write(at,' ',at[r][r][r],'\n');
}
else{
while(!(e[at].count(at[r][r]) && e[at].count(at[r][r][r])))at=at[r];
write(at,' ',at[r],'\n');
write(at,' ',at[r][r],'\n');
write(at,' ',at[r][r][r],'\n');
write(at,' ',at[r][r][r][r],'\n');
}
return 0;
}