501C - Misha and Forest

Solution:

An interesting mix of tree structure and linear algebra. Since we are given the pair \((\text{degree}_v, s_v)\) for each v, we can approach it in an intuitive manner:

1. We will maintain a graph G with vertices v but with no edges just yet. So initially all vertices in G has no neighbouring vertices.

2. Iteratively, we would like to find a vertex v such that the difference between the number of neighbours it currently has and \(\text{degree}_v\) is at most 1. This means that v is short of one vertex. Furthermore, this means that we can determine what vertex is that exactly in O(M) where M is the number of adjacent vertices v currently has, as follows:

We have \(s_v = \text{XOR of all current neighbours of v } u \oplus v'\) where v' is the node we want to find. If we XOR both left hand side and right hand side with \(\text{XOR of all current neighbours of v}\), we will find v'!

We can perform 2 in \(O(N\lg{N}\) using heap structure such as priority queue, and since the final graph is guaranteed to be a tree, the amortized number of operations we need to calculate all the v' is \(O(V)\). A nice problem :)

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <utility> #include <queue> using namespace std; priority_queue<pair<int,int> > st; vector<pair<int,int> > ans; int degree[70000], s[70000]; vector<vector<int> > adj; int N; int main(){ int u,v,w; scanf("%d",&N); for(int i=0;i<N;++i){ scanf("%d %d",&u,&v); st.push(make_pair(-u,i)); degree[i] = u; s[i] = v; } adj = vector<vector<int> >(N+3); while(!st.empty()){ u = st.top().second; v = -st.top().first; w = s[u]; st.pop(); if(degree[u] == adj[u].size())continue; for(int i=0;i<adj[u].size();++i){ w ^= adj[u][i]; } adj[u].push_back(w); adj[w].push_back(u); st.push(make_pair(adj[w].size()-degree[w], w)); ans.push_back(make_pair(u,w)); } printf("%d\n",(int)ans.size()); for(int i=0;i<ans.size();++i){ printf("%d %d\n", ans[i].first, ans[i].second); } return 0; }