流离之人追逐幻影。
好像找不到中文题解啊
有个人在修路，他计划在$n$个城市间修建若干道路使得每个城市的度数都为奇数，而且规定只能在给定的$m$条道路中选择若干条建造
要求使得最长道路最短
输出第$i$行表示只能选择前$i$条道路时的答案
为了不混淆，我们将原图成为图$G$，把修建的路形成的图成为图$T$
先引入一个引理：首先判断能不能度数都为奇数，发现当且仅当$G$的节点数为偶数时才可能
当有奇数个点时，如果每个点度数为奇数，那么总度数为奇数$\times$奇数$=$奇数，而这是不可能的
当有偶数个点时，只需要求出任意一棵生成树，然后从叶子开始一路向上贪心割边，使得除了根以外每个点度数都为奇数（发现这是可以做到的），然后这时我们知道由于整棵树有偶数个点，那么除了根以外有奇数个点，而且这奇数个点度数都为奇数，那么此时除了根以外的点的总度数为奇数，又由于我们知道无向图总度数永远为偶数，所以根的度数此时也必定是奇数。
这个引理不仅可以判断有无解这么简单，它还说明只要我们使得$T$的每一个联通块都包含偶数个点，就一定有办法去掉一些边使得所有点度数都为奇数
这样很容易想到暴力算法：每次将前$i$条边排序，然后跑最小生成森林，直到加进去某条边以后能使得所有联通块大小都为偶数，那么这条边的长度即为答案
为什么呢？因为显然包含奇数个点的联通块数量是永远不会变多的，对于一条边连接的两个联通块来说，奇数连奇数变成偶数，偶数连奇数变成奇数，偶数连偶数变成偶数。
为了方便，下面把度数为奇数的点叫做奇点，偶点、奇联通块、偶联通块的意义也类似。
看到最小生成森林和在线加边，显然会想到用$LCT$试试。每加进去一条边$(u,v)$，如果它连接的两个联通块本来不连通，那就直接$link$，否则如果$w(u,v)$小于树上$u$、$v$间最大边权值，就替换那条最大边。除了以上操作以外，还要额外维护一个加进$LCT$的边的$set$，完成加边后从大到小观察$set$里面的边，如果将这条边断开后形成的两个联通块都是偶联通块，那就删掉它，直到发现一条删掉后会形成奇联通块的边，它就是答案。
关于联通块的大小，似乎需要用$toptree$
杜教优化了一下标算的编程复杂度。定义一条删掉后会形成两个偶联通块的边为偶边，否则为奇边。那么记录$LCT$中每条边的类型，当加进去的边替换了原有的边时，新边和旧边具有相同的类型；不在$u$、$v$路径上的边不会变；在$u$、$v$路径上的边，如果旧边是偶边，则类型不变，否则取反。这个很好证明。然后最大的奇边就是答案。
实现上有点神奇的技巧，主要利用一个引理：随着可用的边增多，答案单调不增。将所有$LCT$中的边加进$set$，每次加完边后在$set$里找小于等于上次答案的最大奇边就可以了。
先离散边权。分治函数$work(l,r,lo,hi)$表示解决$[l,r]$的询问，已知这些询问的答案在$[lo,hi]$中。
使得$mid=\lfloor \frac{l+r}{2} \rfloor$，假设找出了$ans_{mid}$，那么根据上面第二个引理，就可以缩小问题范围并调用$work(l,mid-1,ans_{mid},hi)$和$work(mid+1,r,lo,ans_{mid})$来解决子问题了
要在与$l、r、lo、hi$有关的时间复杂度内求出$ans_{mid}$，需要维护一个可撤销的并查集（按秩合并，可以用一个栈来存储修改，然后一步步撤销栈中的操作），用这个并查集来维护联通块的奇偶信息。在进入递归函数$work(l,r,lo,hi)$之前，保证编号在$[1,l)$且权值在$[1,lo)$的边已经加入并查集。此时要求出$ans_{mid}$，先将编号$[l,mid]$权值$[1,lo)$的边加进并查集，再按照权值从小到大把编号$[1,mid]$权值$[lo,hi]$的边往并查集里面加，直到加进某条边后所有联通块都为欧联通块，这条边就是$ans_{mid}$。找到$ans_{mid}$后撤销刚才的加边。
调用$work(l,mid-1,ans_{mid},hi)$之前要把编号$[1,l)$权值$[lo,ans_{mid})$的边加进去，调用完后撤销。
调用$work(mid+1,r,lo,ans_{mid})$之前要把编号$[l,mid]$权值$[1,lo)$的边加进去，调用完后撤销。
最奇怪的做法，也是灿爷的做法
引理：如果一条编号为$i$的边出现在$ans_j$的最优解中，那么它肯定出现在$[i,j]$的所有最优解中。用算法一可以很好地证明（这似乎不算证明吧，都想到算法一了怎么还会去想这个算法……）
那么暴力地想，每个时刻维护一个并查集，可以先暴力求出$m$的最优解，然后对于最优解中的每条边$i$，都在$[i,m)$的并查集中加入边$i$；然后做$m-1$的最优解……以此类推
发现可以用线段树优化这一线段式覆盖的过程，线段树每个节点开一个$set$，存下所有在该区间内一定出现在最优解中的边。先将所有从小到大边排序放进$ed[]$数组。在线段树上先右儿子后左儿子遍历，同时维护一个可撤销的并查集，进入一个节点的时候把该节点$set$中的边加进并查集，退出的时候撤销掉。每当到达一个叶子（假设时刻为$t$），就从上一个叶子做到的地方开始加$ed[]$中没有考虑过的边，如果可以加就加进来并且更新并查集并且在线段树上用这条边（假设出现时刻为$x$）更新区间$[x,t)$，加边过程在所有联通块都为偶联通块时停止。
总的来说是一道信息量很大的题，可以长点姿♂势♂