politic1

#include <cassert>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX_N = 1000;

// Input parameters
int n;
// Graph structure data
int vNext[MAX_N + 1], visited[MAX_N + 1];
vector<int> v[MAX_N + 1];
// Cycle data
bool inCycle[MAX_N + 1], rootCycle[MAX_N + 1];
int cycleSize[MAX_N + 1];
// DP data
int maxOut[MAX_N + 1][MAX_N + 1], weight[MAX_N + 1];
bool sel[MAX_N + 1];

void computeMaxOut(int node) {
    sel[node] = true;

    assert((inCycle[node] ^ rootCycle[node]) == 0);

    int rootCost = (inCycle[node] ? cycleSize[node] : 1), sons = 0;
    for (auto next : v[node])
        if (!sel[next] && !(inCycle[next] && !rootCycle[next]))
            sons++;

    // if not in cycle, then the current node will be eliminated by the parent
    maxOut[node][rootCost] = (inCycle[node] ? rootCost : 0) + sons;

    if (node == 0) { // eliminating the root does not cost anything and does not affect anything
        maxOut[node][rootCost] = 0;
        rootCost = 0;
    }

    weight[node] = rootCost;

    for (auto next : v[node])
        if (!sel[next] && !(inCycle[next] && !rootCycle[next])) { // don't go over other nodes in the cycle
            computeMaxOut(next);
            weight[node] += weight[next];

            for (int i = weight[node]; i >= rootCost; i--) // total nodes
                for (int j = rootCost; j <= weight[node] - weight[next] && j < i; j++) // how much of it is the part already in node
                    maxOut[node][i] = max(maxOut[node][i], maxOut[node][j] + maxOut[next][i - j]);
        }
}

int main() {
    ifstream fin("politic.in");
    ofstream fout("politic.out");

    // Read input.
    fin >> n;

    assert(1 <= n && n <= MAX_N);

    for (int i = 1; i <= n; i++) {
        fin >> vNext[i];
        v[vNext[i]].push_back(i); // keep reversed edges

        assert(1 <= vNext[i] && vNext[i] <= n);
    }

    // Detect cycles.
    for (int i = 1; i <= n; i++)
        if (!visited[i]) {
            visited[i] = i;

            int node = i;
            while (!visited[vNext[node]]) {
                node = vNext[node];
                visited[node] = i;
            }

            if (visited[vNext[node]] == i) { // have cycle
                rootCycle[node] = true;
                v[0].push_back(node); // edge from overall root (0) to cycle root node

                int currentNode = node, currentCycleSize = 0;
                do {
                    inCycle[currentNode] = true;
                    currentCycleSize++;

                    if (currentNode != node) // merge sons
                        for (auto next : v[currentNode])
                            v[node].push_back(next);

                    currentNode = vNext[currentNode];
                } while (currentNode != node);

                cycleSize[node] = currentCycleSize;
            }
        }

    // Run DP.
    computeMaxOut(0);

    // Get best result.
    int maximumOut = 0;
    for (int i = 1; i <= n; i++) {
        maximumOut = max(min(n, maximumOut + 1), maxOut[0][i]); // can use last result and eliminate one more node
        fout << n - maximumOut << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}