BOJ 25567 줄 세우기

void solve(){
    int N; cin >> N;
    int sz = 0;
    vector<vector<int>> lines;
    rep(i, 0, N){
        int cnt; cin >> cnt;
        vector<int> line(cnt);
        rep(j, 0, cnt) cin >> line[j];
        lines.push_back(line);
        sz += cnt;
    }

    vector<array<int, 3>> Queries; // {query, a, b}
    int Q; cin >> Q;
    rep(i, 0, Q){
        int op, a, b; cin >> op >> a >> b;
        Queries.push_back({op, a, b});
    }

    // lineId[x] = i : x번 사람이 i번째 줄에 속함
    vector<int> lineId(sz+1);
    rep(i, 0, N) for(auto x: lines[i]) lineId[x] = i;

    UnionFind UF(N), UFrev(N);
    vector<int> nxt(N, -1);
    for(auto [op, a, b]: Queries){
        if(op == 2) continue;
        int lineA = lineId[a];
        int lineB = lineId[b];
        if(UF.find(lineA) != UF.find(lineB)){
            // lineA 뒤에 lineB 붙이기
            int tailA = UFrev.find(lineA);
            int headB = UF.find(lineB);
            nxt[tailA] = headB;
            UF.merge(lineA, lineB);
            UFrev.merge(lineB, lineA);
        }
    }

    vector<int> mergedLineId(sz+1);
    vector<int> mergedLineIdx(sz+1);
    vector<vector<ll>> pfsum(N);

    rep(i, 0, N) if(UF.find(i) == i){
        vector<int> order;
        int cur = i;
        while(cur != -1){
            for(auto x: lines[cur]) order.push_back(x);
            cur = nxt[cur];
        }

        for(int j = 0; j < (int)order.size(); j++){
            mergedLineId[order[j]] = i;
            mergedLineIdx[order[j]] = j;
        }
        pfsum[i].resize(order.size()+1);
        rep(j, 0, order.size()) pfsum[i][j+1] = pfsum[i][j] + order[j];
    }

    // 쿼리 처리
    UnionFind UF2(N);
    for(auto [op, a, b]: Queries){
        int lineA = lineId[a];
        int lineB = lineId[b];
        if(op == 1){
            if(UF2.merge(lineA, lineB)) cout << "YES\n";
            else cout << "NO\n";
        }
        else{
            if(UF2.find(lineA) != UF2.find(lineB)){
                cout << "-1\n";
                continue;
            }
            int mergedLine = mergedLineId[a];
            int idxA = mergedLineIdx[a];
            int idxB = mergedLineIdx[b];
            if(idxA > idxB) swap(idxA, idxB);
            cout << pfsum[mergedLine][idxB+1] - pfsum[mergedLine][idxA] << "\n";
        }
    }
}