트리 이진 변환

tree_to_binary.cpp

typedef long long ll;
typedef pair<ll, ll> p;
const int SZ = 303030;
vector<p> inp[SZ], g[SZ*2];

// now, real node, prev, adj list start index
void make_binary(int v = 1, int real = 1, int b = -1, int idx = 0){
    for(int _i=idx; _i<inp[v].size(); _i++){ auto i = inp[v][_i];
        if(i.x == b) continue;
        if(g[real].empty()){
            g[real].emplace_back(i.x, i.y);
            make_binary(i.x, i.x, v);
            g[i.x].emplace_back(real, i.y);
            continue;
        }
        if(_i+1 == inp[v].size() || _i+2 == inp[v].size() && inp[v][_i+1].x == b){
            g[real].emplace_back(i.x, i.y);
            make_binary(i.x, i.x, v);
            g[i.x].emplace_back(real, i.y);
            continue;
        }
        int nxt = ++pv;
        g[real].emplace_back(nxt, 0);
        make_binary(v, pv, b, _i);
        g[nxt].emplace_back(real, 0);
        break;
    }
}