Pastoral Oddities
\(n\) 个点，\(m\) 次操作，每次操作加入一条带权无向边，然后询问当前图中是否存在一个生成子图，满足所有点的度数都是奇数；如果有，输出所有满足条件的生成子图中最大边权的最小值（没有则输出-1）。
\(2\leq n\leq 10^5,1\leq m\leq 3\times 10^5\)。
题解
https://codeforces.com/blog/entry/21885
Hint: What is a necessary and sufficient condition for Kevin to be able to pave paths so that each edge is incident to an odd number of them? Does this problem remind you of constructing a minimum spanning tree?
We represent this problem on a graph with pastures as vertices and paths as edges. Call a paving where each vertex is incident to an odd number of paved edges an odd paving. We start with a lemma about such pavings:
-
A connected graph has an odd paving if and only if it has an even number of vertices.
For connected graphs with even numbers of vertices, we can prove this observation by considering a spanning tree of the graph. To construct an odd paving, start from the leaves of the tree and greedily pave edges so that each vertex but the root is incident to an odd number of paved edges. Now consider the graph consisting only of paved edges. Since the sum of all vertex degrees in this graph must be even, it follows that the root is also incident to an odd number of paved edges, so the paving is odd.
-
Now we prove that no odd paving exists in the case of an odd number of vertices. Suppose for the sake of contradiction that one existed. Then the sum of the vertex degrees in the graph consisting only of paved edges would be odd, which is impossible. Thus no odd paving exists for graphs with odd numbers of vertices.
Note that this observation turns the degree condition into a condition on the parity of connected component sizes. We finish the problem using this equivalent condition.
Suppose we only want to solve this problem once, after all \(m\) edges are added. Then we can use Kruskal's algorithm to build a minimum spanning forest by adding edges in order of increasing length. We stop once each tree in the forest contains an even number of vertices, since the graph now satisfies the conditions of the lemma. If there are still odd-sized components by the time we add all the edges, then no odd paving exists. This algorithm, however, runs in \(O(m\log m)\) per query, which is too slow if we want to answer after adding each edge.
To speed things up, we maintain the ending position of our version of Kruskal's as we add edges online. We do this using a data structure called a link-cut tree. This data structure allows us to add and delete edges from a forest while handling path and connectivity queries. All of these operations take only \(O(\log n)\) time per operation. (A path query asks for something like maximum-weight edge on the path between \(u\) and \(v\); a connectivity query asks if \(u\) and \(v\) are connected.)
First, let's look at how we can solve the online minimum spanning tree problem with a link-cut tree. We augment our data structure to support finding the maximum-weight edge on the path between vertices \(u\) and \(v\) in \(O(\log n)\). Adding an edge then works as follows: If u and v are not connected, connect \(u\) and \(v\); otherwise, if the new edge is cheaper, delete the maximum-weight edge on the path between u and v and add the new edge. To make implementation easier, we can represent edges as vertices in the link-cut tree. For example, if \(u\) and \(v\) are connected, in the link-cut tree they would be connected as \(u--e--v\), where \(e\) is a vertex representing edge \(u--v\).
We solve our original problem with a similar idea. Note that the end state of our variation on Kruskal's is a minimum spanning forest after adding \(k\) edges. (We no longer care about the edges that are longer than the longest of these \(k\) edges, since the answer is monotonically decreasing---more edges never hurt.) So when we add another edge to the forest, we can use the online minimum spanning tree idea to get the minimum spanning forest that uses the old cheapest \(k\) edges and our new edge. Note that inserting the edge never increases the number of odd components: even linked to even is even, even linked to odd is odd, odd linked to odd is even.
Now, pretend that we got this arrangement by running Kruskal's algorithm, adding the edges one-by-one. We can "roll back" the steps of the algorithm by deleting the longest edge until deleting another edge would give us an odd-sized component. (If we started with an odd-sized component, we don't delete anything.) This gives us an ending position for our Kruskal-like algorithm that uses a minimal number of edges so that all components have even size---we're ready to add another edge. ("But wait a minute!" you may say. "What if edges have the same weight?" In this case, if we can't remove one of possibly many longest edges, then we can't lower our answer anyway, so we stop.)
Note that all of this takes amortized \(O(\log n)\) time per edge. The path queries and the insertion of the new edge involve a constant number of link-cut tree operations. To know which edge to delete, the set of edges currently in the forest can be stored easily in an STL set sorted by length. When adding an edge, we also pay for the cost of deleting that edge, so the "rolling back" phase gets accounted for. Therefore, this algorithm runs in \(O(m\log n)\).
You may have noticed that executing this algorithm involves checking the size of a connected component in the link-cut tree. This is a detail that needs to be resolved carefully, since link-cut trees usually only handle path operations, not operations that involve subtrees. At each vertex, we track the size of its virtual subtree, as well as the sum of the real subtree sizes of its non-preferred children. We can update these values while linking and exposing (a.k.a. accessing), allowing us to perform root-change operations while keeping real subtree sizes. To get the size of a component, we just query for the real subtree size of the root.
CO int N=4e5+10;
int ch[N][2],fa[N],rev[N];
int val[N],mx[N]; // node with the maximum value
int wei[N],siz[N]; // weight for non-preferred children
IN bool nroot(int x){
return ch[fa[x]][0]==x or ch[fa[x]][1]==x;
}
IN int cmp(int x,int y){
return val[x]>=val[y]?x:y;
}
IN void reverse(int x){
swap(ch[x][0],ch[x][1]),rev[x]^=1;
}
IN void push_up(int x){
mx[x]=cmp(x,cmp(mx[ch[x][0]],mx[ch[x][1]]));
siz[x]=wei[x]+siz[ch[x][0]]+siz[ch[x][1]];
}
IN void push_down(int x){
if(rev[x]){
reverse(ch[x][0]),reverse(ch[x][1]);
rev[x]=0;
}
}
IN void rotate(int x){
int y=fa[x],z=fa[y],l=x==ch[y][1],r=l^1;
if(nroot(y)) ch[z][y==ch[z][1]]=x;fa[x]=z;
ch[y][l]=ch[x][r],fa[ch[x][r]]=y;
ch[x][r]=y,fa[y]=x;
push_up(y);
}
void splay(int x){
vector<int> stk={x};
for(int i=x;nroot(i);) stk.push_back(i=fa[i]);
for(;stk.size();stk.pop_back()) push_down(stk.back());
for(;nroot(x);rotate(x)){
int y=fa[x],z=fa[y];
if(nroot(y)) rotate((x==ch[y][1])!=(y==ch[z][1])?x:y);
}
push_up(x);
}
void access(int x){
for(int y=0;x;y=x,x=fa[x]){
splay(x);
wei[x]+=siz[ch[x][1]];
ch[x][1]=y;
wei[x]-=siz[y],push_up(x);
}
}
IN void make_root(int x){
access(x),splay(x),reverse(x);
}
IN void link(int x,int y){
make_root(x),fa[x]=y;
wei[y]+=siz[x],push_up(y);
}
IN void cut(int x,int y){
make_root(x),access(y),splay(y),fa[x]=ch[y][0]=0;
push_up(y);
}
IN int path_max(int x,int y){
make_root(x),access(y),splay(y);
return mx[y];
}
IN int size(int x){
make_root(x);
return siz[x];
}
IN bool connected(int x,int y){
access(x),splay(x),access(y),splay(y);
return fa[x]!=0;
}
struct edge {int u,v,w,i;} eg[N];
IN bool operator<(CO edge&a,CO edge&b){
return a.w!=b.w?a.w>b.w:a.i<b.i;
}
set<edge> s;
int main(){
int n=read<int>(),m=read<int>(),o=n;
function<int(CO edge&)> delete_edge=[&](CO edge&e)->int{
cut(e.u,e.i+n),cut(e.v,e.i+n);
if(size(e.u)%2==1 and size(e.v)%2==1) o+=2;
return size(e.u)%2==0; // can't delete the edge only when both components are odd
};
function<void(CO edge&)> add_edge=[&](CO edge&e)->void{
if(size(e.u)%2==1 and size(e.v)%2==1) o-=2;
link(e.u,e.i+n),link(e.v,e.i+n);
};
function<void(CO edge&)> new_edge=[&](CO edge&e)->void{
val[e.i+n]=e.w;
wei[e.i+n]=siz[e.i+n]=0;
if(connected(e.u,e.v)){
int x=path_max(e.u,e.v);
if(val[x]<=e.w) return;
delete_edge(eg[x-n]);
s.erase(eg[x-n]);
}
add_edge(e);
s.insert(e);
};
function<int()> max_cost=[&]()->int{
if(o>0) return -1;
while(delete_edge(*s.begin()))
s.erase(s.begin());
add_edge(*s.begin());
return s.begin()->w;
};
for(int i=1;i<=n;++i){
val[i]=0;
wei[i]=siz[i]=1;
}
for(int i=1;i<=m;++i){
int u=read<int>(),v=read<int>(),w=read<int>();
new_edge(eg[i]={u,v,w,i});
printf("%d\n",max_cost());
}
return 0;
}