CF603E 题解
Saliеri
2021-03-18 18:42:01
来一篇写得清楚一点的线段树分治。
___
首先我们考虑这个题目的限制 ，`每个点的度数都是奇数` ，的本质是什么。
手玩几个图，珂以发现一个很强的结论：
这个限制等价于 “这个图中只存在大小为**偶数**的连通块”。
证明：
- 必要性：假设存在奇数大小的连通块，由于每个点的度数都为奇数，所有所有度数之和也为奇数。然而每一条边都对总度数贡献且只贡献了 **2**，所以**总度数必然是偶数**。这就与假设矛盾。所以只有必然只存在偶数大小的连通块。
- 充分性：对于每一个偶数大小的连通块，随便拿出它的一颗生成树，从底向上跑一遍这个算法：
- 如果这个节点儿子连上来的边数为偶数，就连上他与父亲的边，反之则不然。
我们发现，这样的构造可以满足除了根的所有节点的限制。
然而因为这个连通块内除根外其他节点的数量是奇数，而这些点的度数都是奇数，而包括根的总度数是偶数，所以根的度数自然也是奇数。
证明完结论后，就可以开始考虑 `最小化边集中的最大边权` 的这个限制了。
很明显，这个条件一看就很有**最小瓶颈生成树**的感觉，而最小瓶颈生成树的解决方式应该人人皆知。Kruskal，即按权值从小到大加边直到满足条件为止。
~~这个题应该不会有人因为在这里想到 Prim 然后掉进粪坑吧~~
到这里我们就可以得到这个问题的静态版本的解法：
- **把边按权值排序**，用并查集时刻维护一下奇连通块的数目就行了。
接下来我们考虑怎么把这个算法扩展到动态加边。
不难想到的是，这个算法想要支持动态加边且保证复杂度基本是胡扯。
因为在排序后的边集的中间加边就可能会导致整张图的形态从那里开始变化，从而影响答案，而这个影响我们是无法快速算出的。
但如果我们仔细考虑一下加边的过程，发现：一条边如果进入时就没有进入最优边集，那么就再也不会进入；一条边一旦被淘汰，就再也不会回来。
说明：每一条边有一个影响范围，只有这个范围内这条边才会被纳入最优边集中。
**影响范围 & 时间轴 -> 线段树分治。**
接下来就考虑怎么求出每条边的影响区间。
考虑在线段树分治的过程中，每访问到一个叶子，我们都必然需要后移 Kruskal 的指针，将新的合法的边纳入答案直到合法为止。那么这个时间点就是这条边的影响范围的结束位置，而我们又知道每一条边的出现时间，于是事情就好起来了。
注意：分治时应当**从右到左**递归，因为我们是要依次对每一个时间点求出答案，然后通过答案计算被最优边集包含的边影响区间。如果从左到右的话，得不到每一条边的影响区间的结束位置。
但是我们发现这是一个边分治边 cover 的处理过程，直接线段树分治起来可能会有点小问题，因为这个时间点上 cover 上的边不知道什么时候撤回掉。
这也很简单啊，只 cover 到当前时间减一就可以了，这个点上 cover 上的边在这个点直接撤回就完事了。
这个算法的原理也很好理解：
我们每次在叶子节点找答案，祖先节点上 cover 上的时间戳必然合法，在这个点上 cover 上的边也会因为判断而只加起始时间在当前时间点之前的边。
原本我们的时间复杂度因为每一次暴力加边而变得不可接受。
而通过计算决策的影响范围与将这些范围线段树分治，就减少了大量的重复计算。
总的复杂度还是经典的 $O(m \log m \log n)$。
___
代码区：
自认为代码写的比较好看……
```cpp
#include <cstdio>
#include <vector>
#include <algorithm>
const int maxn = 3e5+5;
int n,m,pos,ans[maxn],odd;
struct Edge{
int x,y,v,id;
bool operator <(Edge b){return v<b.v;}
}e[maxn];
struct ch{int x,y,dlt;};
ch st[maxn];
int fa[maxn],siz[maxn],top;
int getfa(int x){return fa[x] == x ? x : getfa(fa[x]);}
std :: vector <Edge> vec[maxn<<2];
void cover(int k,int l,int r,int x,int y,Edge v){
if(l>y||r<x||x>y)return ;
if(l>=x&&r<=y)return vec[k].push_back(v),void();
int mid = l+r>>1;
cover(k<<1,l,mid,x,y,v),cover(k<<1|1,mid+1,r,x,y,v);
}
void trymerge(int x,int y){
int fx = getfa(x),fy = getfa(y);
if(fx != fy){
if(siz[fx]<siz[fy])fx^=fy^=fx^=fy;
st[++top] = (ch){fx,fy,0};
if(siz[fx]%2==1&&siz[fy]%2==1)odd-=2,st[top].dlt+=2;
siz[fx] += siz[fy],fa[fy] = fx;
}
}
void getans(int k,int l,int r){
int pretop = top;
for(int i=0;i<vec[k].size();++i)trymerge(vec[k][i].x,vec[k][i].y);
int mid = l+r>>1;
if(l == r){
while(1){
if(odd == 0 || pos == m)break;
if(e[pos+1].id <= l){
trymerge(e[pos+1].x,e[pos+1].y);
cover(1,1,m,e[pos+1].id,l-1,e[pos+1]);
}
++pos;
}
if(odd == 0)ans[l] = e[pos].v;
else ans[l] = -1;
}
else getans(k<<1|1,mid+1,r),getans(k<<1,l,mid);
while(top^pretop){
int x = st[top].x,y = st[top].y,dlt=st[top].dlt;
siz[x] -= siz[y],fa[y] = y,odd += dlt,--top;
}
}
int main(){
scanf("%d %d",&n,&m),odd = n;
for(int i=1;i<=n;++i)fa[i] = i,siz[i] = 1;
for(int i=1;i<=m;++i)scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].v),e[i].id = i;
std::sort(e+1,e+m+1),getans(1,1,m);
for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
return 0;
}
```