当 \(n\) 为奇数的时候，\(\sum deg\) 是奇数，但显然它应该是偶数，换言之 \(n\) 为奇数一定无解。
事实上只要一个连通块是偶数它内部就有解：只用考虑一颗树，我们从叶子开始确定每个点和父亲的连边是否选中即可。和一道 div2 E Tree Sum 非常类似。
也就是有解等价于每个连通块大小是偶数。
最大值最小这个条件容易想到二分，但是有多个询问所以我们采用整体二分。
问题在于这里的询问不是互相独立的，但注意到由于询问单调，所以任意时刻我们关心的询问都是一段区间。即，在一般的整体二分中，对于答案区间 \([x,y]\)，相关的询问是一个集合 \(S\)，但是在本题中因为询问答案的单调性，所以相关询问一定也构成一个区间 \([l,r]\)。
也就是我们可以设计这样一个函数 solve(x,y,l,r) 表示询问 \([l,r]\) 的答案全部落在 \([x,y]\) 范围内；我们找到 \(mid=\frac{x+y}{2}\)，找到第一个答案小于等于 \(mid\) 的询问 \(pos\)，则划分成了两段 solve(x,mid,pos,r) 和 solve(mid+1,y,l,pos-1)。
那么所有边权 \(\lt x\) 且出现时间 \(\lt l\) 的边都应该预先加入，然后我们首先加入出现时间 \(\lt l\) 且边权 \(\le mid\) 的边，然后从 \(l\) 开始枚举边，在边权 \(\le mid\) 时加入，如果某个时刻变得合法了，那么它就是我们找到的 \(pos\) 位置。
这个做法的计算量只是和 \(y-x\) 以及 \(r-l\) 相关的，也就是从答案区间的视角来看每一层的总和是 \(2m\) 这个级别。然后我们要维护的是一个可撤销并查集所以就 \(O(m\log^2 m)\) 了。
标签：询问,mid,pos,2023.2,lt,solve,边权 From： https://www.cnblogs.com/Cry-For-theMoon/p/17090925.html