【最小生成树&LCT】Codeforces603E-Pastoral Oddities_codeforces 区间最小生成树 lct

题目大意：

给出一个图，求使得这个图中每个点的度数都为奇数。
求出用前i条边，使图满足条件的情况下，最大边权的最小值。

---

分析：

SolutionA LCT维护最小生成树

很容易发现一些性质：
如果要使得图中每个点度数为奇数，那么每个联通块中点的个数一定为偶数：

根据题目，为了使最大边权最小，我们可以把每个联通块看成它的最小生成树，那么这棵树一定满足：每个非根节点的儿子结点个数必须为偶数，根节点儿子结点个数必为奇数。否则就会出现度数为奇的情况。

那么我们可以这么考虑：首先根节点的儿子结点个数为奇，那么加上他自己，与根节点直接相连的点的个数就为偶数。每个非根结点都会为树增加偶数个子节点，所以最终整个树上的点一定为偶数个。

为了使图中的所有联通块大小都为偶数，
我们可以发现，加边是绝对无害的：
因为：奇数图+奇数图=偶数图，奇数图+偶数图=奇数图，偶数图+偶数图=偶数图。
所以可见我们要尽量加边。
当然，如果边的两端在同一联通块，我们就要找到环上的最大边权，与当前边权比较，看能否替换掉。

满足每个点度数都为奇数后，
为了使最大边权尽量小，我们也必须拆边，显然，拆边不能使图中生成奇数图，所以每次删去最大的边，再判断一次是否合法即可。

现在，我们需要动态地插边和删边，并询问路径上的最大边权，以及询问联通块大小。能做到的这些操作的数据结构，显然使用LCT。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define SF scanf
#define PF printf
using namespace std;
void Read(int &x){
    char c;
    bool flag=0;
    while(c=getchar(),c!=EOF&&(c<'0'||c>'9')&&c!='-');
    if(c=='-'){c=getchar();flag=1;}
    x=c-'0';
    while(c=getchar(),c!=EOF&&c>='0'&&c<='9')x=x*10+c-'0';
    if(flag==1)x=-x;
}

#define MAXN 100010
#de
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20