考虑原图是一条链的情况——

思路：随机一个点$x$，将其所在段（边集）再划分为两段，重复此过程即可得到该链

实现上，（从左到右）维护每一段的左端点和边集，二分找到最后一个删除后$x$到根不连通的段，那么其即是$x$所在段，再暴力枚举段中每一条边划分即可

前者二分显然为$o(n\log n)$，后者即是一个类似于sort/treap的结构，总期望次数为$o(n\log n)$

最终，总查询次数为$o(n\log n)$，可以通过

考虑原图是一棵树的情况——

思路：以0为根建树，求出一个链剖分的结果（链上存储点集、边集和链顶父亲所在的链），再利用链的做法求出链上点和边具体的顺序，最后将所有链组合即可得到该树

实现上，根据思路分为两部分（求链剖分和求原树）：

求链剖分时，对每一条链维护边集、部分点集（仅考虑已经加入的点）和链顶父亲所在的链，并按照剖分顺序依次编号，那么加入一个点$x$，按以下方式处理——

找到剩余边中在$x$到根路径上的边，这可以通过不断二分实现（即找到第一条满足删除后$x$到根不连通的边，直接二分不具备单调性，那么将其前缀均删除即可），接下来有两种情况：

1.不存在这样的边，即$x$在某条链上，二分找到编号最大的链满足删除后$x$到根不连通，那么其即是$x$所在链，将$x$加入该链的点集即可

2.存在这样的边，这些边必然是$x$到根路径上的一个前缀，即得到了一条新的链，而此时1中的二分即会求出该链链顶父亲所在的链

（这里直接二分同样不具备单调性，将其后缀均删除即可）

求原树时，对每一条链在其链顶的父亲所在的链中二分找到具体的父亲即可

除了求链剖分中"不断二分/分治"外，其余均为直接二分显然为$o(n\log n)$，前者考虑每条边至多被得到一次，进而均摊总询问次数为$o(n\log n)$

最终，总查询次数为$o(n\log n)$，可以通过

结合上面两个做法，来考虑原问题——

思路：求出一棵生成树，再求出所有非树边

实现上，根据思路同样分为两部分（求生成树和非树边）：

求生成树时，可以参考树的做法，唯一不同的即在于$x$到根路径并不唯一，那么改为找到第一条满足将其以及其之前的边均删除后$x$到根不连通的边即可（这与之前的二分实现上一样）

（可以理解为从前往后尽量删去当前边，并通过二分优化此过程）

另外，当前的非树边默认已经被删除，下同

求非树边时，按dfs序从后往前考虑点$x$，一条非树边以$x$为一个端点当且仅当将$x$到父亲的边删除、将这条边加入后$x$到根不连通，同样可以二分实现

找到边后，还需要求出该边另一个端点，也即求dfs序最大的点满足将其和$x$到父亲的边删除、将这条边加入后$x$到根仍连通，同样也可以二分实现

（这里的两个二分同样不具备单调性，将其前缀/后缀均加入/删除即可）

重复此过程也即可得到所有非树边，询问次数的分析与之前类似

最终，总查询次数为$o(m\log n)$，可以通过

1 #include
2 #include"graph.h"
3 using namespace std;
4 #define N 605
5 #define pii pair
6 int n,m,t,vis[N],fa[N],Fa[N],dfn[N];
7 vectorVis,v[N],e[N];
8 vectorans;
9 void clear(int p){
10 for(int i=0;iv;
19 for(int i=0;i>1);
27 clear(1);
28 for(int i=0;i<=mid;i++)Vis[v[i]]=0; 29 if (query(k,Vis))l=mid+1; 30 else r=mid; 31 } 32 return v[l]; 33 } 34 int find2(int k){ 35 init_tree(); 36 for(int i=1;i>1);
42 init_tree();
43 for(int i=mid;i>1);
54 init_tree();
55 Vis[e[k][mid]]=0;
56 if (query(x,Vis))r=mid-1;
57 else l=mid;
58 }
59 return v[k][l];
60 }
61 int find4(int k){
62 vectorv;
63 for(int i=0;i>1);
72 init_tree();
73 for(int i=0;i<=mid;i++)Vis[v[i]]=1; 74 Vis[Fa[k]]=0; 75 if (query(k,Vis))r=mid; 76 else l=mid+1; 77 } 78 return v[l]; 79 } 80 int find5(int k,int x){ 81 int l=1,r=n; 82 while (l>1);
84 init_tree();
85 for(int i=mid;i<=n;i++)Vis[Fa[dfn[i]]]=0; 86 Vis[x]=1; 87 if (query(k,Vis))r=mid-1; 88 else l=mid; 89 } 90 return dfn[l]; 91 } 92 void calc(int k){ 93 vectorv0,fa[N];
94 random_shuffle(v[k].begin()+1,v[k].end());
95 v0.push_back(v[k][0]);
96 for(int i=0;i>1);
102 init_tree();
103 for(int j=0;je0;
108 for(int j=0;j solve(int nn,int mm){
121 srand(time(0));
122 n=nn,m=mm;
123 for(int i=0;i1;i--)
152 while (1){
153 int x=find4(dfn[i]);
154 if (x<0)break;
155 vis[x]=-1,ans[x]=make_pair(dfn[i],find5(dfn[i],x));
156 }
157 return ans;
158 }