[code source] daily question tree

2022.05.07

Topic link ： Trees - subject - Daimayuan Online Judge

Title Description ：

There is a tree n The number of nodes is in 11 For rooted trees . You can now operate on this tree several times , Each operation can select a point in the tree and delete all edges between the point and its son .

Now I want to know for every k∈[1,n], At least how many operations are needed to make the graph happen to exist k A link block .

Input format

Enter a positive integer in the first line n.

Second line input n−1 It's an integer fi Express i+1 Father of point , Guarantee 1≤fi≤i.

Output format

Output n It's an integer , The first i The number means k=i The answer is , If you can't make the graph just exist k A link block , The output -1.

The sample input

6
1 2 1 1 2

Sample output

0 -1 1 1 -1 2

Data scale

common 10 A test point .

Test point 1,2,31,2,3 Satisfy n≤20.

Test point 4,5,64,5,6 Satisfy n≤100.

For all the data , Satisfy 1≤n≤3000.

analysis ：

Delete a node , The number of connected blocks increases the number of child nodes of the node . that , We regard each node as an object , The value of an item is the number of child nodes . The knapsack capacity is the number of connected blocks .

f[i] Express i The minimum number of operations required for connected blocks .

Transfer equation ：f[i]=min(f[i],f[i-a[i]]+1).

See the code for details. ：

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
#define ll long long
int n, a[3009], f[3009];
void solve()
{
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        int x;
        cin >> x;
        a[x]++; // Count the number of child nodes 
    }
    memset(f, 127, sizeof(f)); // The initial setting is infinite 
    f[1] = 0;                  // Initial is 1 A connecting block , Without the operating 
    for (int i = 1; i <= n; i++)
    {
        if (a[i]) // Has child nodes 
        {
            for (int j = n; j >= a[i]; j--)
            {
                f[j] = min(f[j], f[j - a[i]] + 1); // 01 knapsack 
            }
        }
    }
    for (int i = 1; i <= n; i++) // Output 
        if (f[i] < 9999999)
            cout << f[i] << " \n"[i == n];
        else
            cout << -1 << " \n"[i == n];
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
}