- 给定一棵(n)个点的仙人掌。
- 初始每个点自成一个点集，所有点颜色都为(1)，你可以进行三种操作：合并两个点(x,y)所在的点集；在点集(x)中(a,b)两种颜色的点之间两两连边；把点集(x)中所有颜色为(a)的点的颜色修改为(b)。
- (nle5 imes10^4)
圆方树
遇上仙人掌题目首先无脑构造一棵圆方树。
对于方点的构造
对于方点，我们的目的是把所有子节点按顺序连成一条链，并给两个端点标上与其他点不相同的颜色。
我们维护一条链(1-2-2-...-2-3)，其中(1)表示链首，(2)表示中间不再连边的普通点，(3)表示链尾。
注意，子节点子树内除自己外的其他点同样不再连边，也应当标记成(2)，否则会对连边造成干扰。
新加入的点我们先标记成(4)，合并点集后在(3,4)之间连边，然后把(3)修改成(2)，把(4)修改成(3)。
最后我们把(3)修改成(1)，就满足除了链首和链尾为(1)以外，其余所有点都是(2)。
对于圆点的构造
对于圆点，我们的目的是把所有子节点的对应链都接到当前点上。
我们先合并所有子节点的点集，由于链首和链尾颜色都是(1)，我们先把(1)修改成(4)，然后与当前点合并，在(1,4)之间连边就完成了连边任务。
最后我们把(4)修改成(2)，就满足除了当前点为(1)以外，子树内其余点都是(2)。
代码：(O(m))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 50000
#define M 2000000
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
int n,m,tot,ee,lnk[N+5];struct edge {int to,nxt;}e[2*M+5];
namespace FastIO
{
#define FS 20000000
#define tc() (*FA++)
#define pc(c) (*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void Input() {FB=(FA=FI)+fread(FI,1,FS,stdin);}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void write(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);}
I void OP_j(CI x,CI y) {++tot,pc('j'),pc(' '),write(x),pc(' '),write(y),pc('
');}
I void OP_r(CI x,CI y,CI z) {++tot,pc('r'),pc(' '),write(x),pc(' '),write(y),pc(' '),write(z),pc('
');}
I void OP_c(CI x,CI y,CI z) {++tot,pc('c'),pc(' '),write(x),pc(' '),write(y),pc(' '),write(z),pc('
');}
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
}using namespace FastIO;
namespace RST//圆方树
{
#define nadd(x,y) (ne[++nee].nxt=nlnk[x],ne[nlnk[x]=nee].to=y)
int ct,d,dfn[N+5],low[N+5],f[N+5],nee,nlnk[2*N+5];edge ne[4*N+5];
I void Build(CI x,RI y) {++ct;W(nadd(ct,y),nadd(y,ct),y^x) y=f[y];}//新建一个方点
I void Tarjan(CI x) {dfn[x]=low[x]=++d;for(RI i=lnk[x],y,t;i;i=e[i].nxt) (y=e[i].to)^f[x]&&//建树
((t=dfn[y]?dfn[y]:(f[y]=x,Tarjan(y),low[y]))>dfn[x]?(Build(x,y),0):low[x]=min(low[x],t));}//判断是否产生环
int s[N+5],id[2*N+5];I void dfs(CI x,CI lst=0)//遍历一遍
{
RI i,t=0;for(i=nlnk[x];i;i=ne[i].nxt) ne[i].to^lst&&(dfs(ne[i].to,x),0);
for(i=nlnk[x];i;i=ne[i].nxt) ne[i].to^lst&&(s[++t]=ne[i].to);//按顺序存下子节点
if(x>n)//对于方点
{
if(id[x]=s[t],t==1) return;//只有一个子节点时无需操作
for(i=2;i<=t;++i) OP_r(s[i],1,4),OP_j(s[i-1],s[i]),//把要加入的点标记为4，然后合并
i^2?(OP_c(s[i],3,4),OP_r(s[i],3,2)):OP_c(s[i],1,4),OP_r(s[i],4,3);//连边然后将原本的3改为2（特殊处理与链首连边），把4改为3
return OP_r(s[t],3,1);//把3改为1，使得除链首和链尾为1外其余都是2
}
if(!t) return;for(i=2;i<=t;++i) OP_j(id[s[i-1]],id[s[i]]);//把所有子节点的点集合并
OP_r(id[s[1]],1,4),OP_j(x,id[s[1]]),OP_c(x,1,4),OP_r(x,4,2);//把子节点的1改为4，合并后在1,4间连边，然后把4修改为2，使得除当前点为1外其余都是2
}
}
int main()
{
RI i,x,y,z;for(Input(),read(n,m),i=1;i<=m;++i) {read(x,y);W(--x) read(z),add(y,z),add(z,y),y=z;}
return RST::ct=n,RST::Tarjan(1),RST::dfs(1),printf("%d
",tot),clear(),0;
}