这个题做法目前来看有三种：
1.LCT维护最小生成树；
2.cdq分治（或整体二分）；
3.线段树分治
实际上第2种方法是最好写的......不过就是跑的有点慢（应该是我的写法问题）。
那接下来就介绍一下第二种写法吧（
首先可以发现，一个连通块是满足条件的，当且仅当连通块的点数为偶数。
也就是说，连通块的点数为奇数时就不行。由此可见，当 $n\bmod 2==1$ 时答案全都为 $-1$。
然后这个题要求所有合法连通块中最大的边（这题非要把 edge 说成 path，导致我一开始以为是要求最长最短路最短禁止套娃）。所以不难想到，我们所需要的边一定在这个连通块的最小生成树上。
我们首先将所有的边按照权值从小到大排序，像Kruskal那样。
考虑分治：我们令 $solve(l,r,low,up)$ 表示当前处理的区间为 $[l,r]$，答案的区间为 $[low,up]$。接下来，就考虑怎么统计答案。
考虑Kruskal算法：我们需要用并查集来维护这棵树，这道题我们也可以用相同的方法，不过由于会带有删边操作（将 $x$ 到其父亲 $fx$ 这条边删掉），那么我们的并查集也就得支持撤销操作，所以不能写路径压缩。为了优化，我们可以将按秩合并优化放上去，即将小树接到大树的根上，这样均摊下来复杂度不会太高。
然后就是分治过程：每一次我们计算 $mid=(l+r)>>1$ 的答案。由于我们当前要计算的答案区间为 $[low,up]$，那么 $[l,mid]$ 的这些边中，可能会有一些边的权值小于等于 $low$。可以发现：对于一个连通块，连的边越多越好（连通块合法的前提下）。那么我们就将这些边加上去，对应的点就用并查集搞起来。之后，我们再将权值在 $[low,up]$ 中的边从小到大依次加进去，用 $cnt$ 记录不合法的连通块数量（$cnt$ 一开始为 $n$），那么加完边或者加到中间 $cnt=0$ 的话说明当前存在一个合法方案，答案就是最后加的那条边的权值。
然后就是cdq分治或者整体二分的套路了：我们将并查集过程中更新过的这些根用一个栈存起来，每一次统计完就将这些点与其父亲相连的边删掉即可，否则会重复统计答案。
代码中 $low$ 和 $up$ 并没有直接代表权值，而是相当于将权值离散化一下得到的权值下标之类的东西。这样可以优化一点常数。
......不过仍然比较慢就是了。
#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=300050;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
int f[N];
int n,m,cnt,h;
ll ans[N];
int s[N],siz[N];
struct edge
{
int x,y;ll w;
int id;
}e[N],g[N];
inline bool cmp(const edge &x,const edge &y)
{
return (x.w==y.w)?x.id<y.id:x.w<y.w;
}
inline void Union(int x,int y)
{
int rkx=0,rky=0;
while(x!=f[x])x=f[x],rkx++;
while(y!=f[y])y=f[y],rky++;
if(x==y)return;
if(rkx>rky)swap(x,y);
cnt-=(siz[x]&1)+(siz[y]&1)-((siz[x]+siz[y])&1);
f[x]=y;siz[y]+=siz[x];
s[++h]=x;
}
inline void del(int x)
{
int fx=f[x];
siz[fx]-=siz[x];f[x]=x;
cnt+=(siz[fx]&1)+(siz[x]&1)-((siz[x]+siz[fx])&1);
}
void solve(int l,int r,int low,int up)
{
if(l>r)return;
int mid=(l+r)>>1,las=h,ansmid=low;
int id=e[mid].id;
for(int i=l;i<=mid;++i)
if(e[i].w<=low)Union(e[i].x,e[i].y);
for(int i=low;i<=up&&cnt;++i,ansmid++)
if(g[i].id<=mid)Union(g[i].x,g[i].y);
ansmid=max(low,ansmid-1);
if(cnt==0)ans[id]=g[ansmid].w;
else ans[id]=-1;
while(h>las)del(s[h]),h--;
for(int i=low;i<=ansmid;++i)
if(g[i].id<=l)Union(g[i].x,g[i].y);
solve(l,mid-1,ansmid,up);
while(h>las)del(s[h]),h--;
for(int i=l;i<=mid;++i)
if(e[i].w<=low)Union(e[i].x,e[i].y);
solve(mid+1,r,low,ansmid);
while(h>las)del(s[h]),h--;
}
int main()
{
cin>>n>>m;cnt=n;
for(int i=1;i<=n;++i)f[i]=i,siz[i]=1;
if(n&1){for(int i=1;i<=m;++i)puts("-1");return 0;}
for(int i=1;i<=m;++i)
{
scanf(
e[i].id=i;g[i]=e[i];
}
sort(g+1,g+m+1,cmp);
for(int i=1;i<=m;++i)e[g[i].id].w=i;
solve(1,m,1,m);
for(int i=1;i<=m;++i)printf(
return 0;
}
Comments NOTHING