문제

https://www.acmicpc.net/problem/13512


알고리즘

DP


풀이

트리 위에서 두 가지 쿼리를 진행해야 합니다. 첫 번째는 $i$번째 정점의 색을 바꾸는 것. 두 번째는 1번 정점에서부터 $v$정점까지 가는 경로 중 첫 번째로 만나는 검은 정점의 번호를 출력하는 것입니다.

트리에서는 문제를 풀기가 어려우므로 HLD를 이용해서 쭉 펴도록 합시다. 일자 상태로 만들었다면 세그먼트 트리의 사용이 가능해집니다. 세그먼트 트리에서 인덱스가 작을수록 트리 위에서는 루트에 가깝습니다. 이러한 이유 때문에 $query$함수에서 세그먼트 트리 쿼리를 처리할 때, 왼쪽에 검은 정점이 있다면 바로 리턴을 했습니다. 오른쪽에 있는 구간은 왼쪽보다 루트로부터 멀기 때문입니다(처음으로 만나는 검은 정점이 아님).

세그먼트 트리의 리프노드에는 흰 정점이라면 0을 검은 정점이라면 해당 번호를 적어놓고 풀었습니다.

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N, M;
vector<int> pick, vt;
bool used[10005];
void solve(int m) {
    if (m == 0) {
        for (auto val : pick) {
            cout << val << ' ';
        }
        cout << '\n';
        return;
    }
    bool level_used[10005] {};
    rep(i, N) {
        if (!used[i] && !level_used[vt[i]]) {
            used[i] = true;
            level_used[vt[i]] = true;
            pick.emplace_back(vt[i]);
            solve(m - 1);
            pick.pop_back();
            used[i] = false;
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> M;
    vt.resize(N);
    rep(i, N) {
        int& x = vt[i];
        cin >> x;
    }
    sort(vt.begin(), vt.end());
    solve(M);
    return 0;
}