Codeforces Round 285 (Div. 2 C or Div. 1 A) - Misha and Forest

Problem Statement:
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;
}