Beech Tree

beechtree
English (ISC)
Beech Tree
Vétyem Woods is a famous woodland with lots of colorful trees. One of the oldest and tallest beech
trees is called Ős Vezér.
The tree Ős Vezér can be modeled as a set of N nodes and N −1 edges. Nodes are numbered
from 0 to N −1 and edges are numbered from 1 to N −1. Each edge connects two distinct nodes
of the tree. Specifically, edge i (1 ≤i < N) connects node i to node P[i], where 0 ≤P[i] < i.
Node P[i] is called the parent of node i, and node i is called a child of node P[i].
Each edge has a color. There are M possible edge colors numbered from 1 to M . The color of
edge i is C[i]. Different edges may have the same color.
Note that in the definitions above, the case i = 0 does not correspond to an edge of the tree. For
convenience, we let P[0] = −1 and C[0] = 0.
For example, suppose that Ős Vezér has N = 18 nodes and M = 3 possible edge colors, with 17
edges described by connections P = [−1,0,0,0,1,1,1,2,2,3,3,3,4,4,5,10,11,11] and colors
C = [0,1,2,3,1,2,3,1,3,3,2,1,1,2,2,1,2,3]. The tree is displayed in the following figure:
Árpád is a talented forester who likes to study specific parts of the tree called subtrees. For each r
such that 0 ≤r < N, the subtree of node r is the set T® of nodes with the following properties:
beechtree (1 of 6)

Node r belongs to T®.
Whenever a node x belongs to T®, all children of x also belong to T®.
No other nodes belong to T®.
The size of the set T® is denoted as ∣T®∣.
Árpád recently discovered a complicated but interesting subtree property. Árpád's discovery
involved a lot of playing with pen and paper, and he suspects you might need to do the same to
understand it. He will also show you multiple examples you can then analyze in detail.
Suppose we have a fixed r and a permutation v ,v ,... ,v
of the nodes in the subtree T®.
For each i such that 1 ≤i < ∣T®∣, let f(i) be the number of times the color C[v ] appears in the
following sequence of i −1 colors: C[v ],C[v ],... ,C[v
].
(Note that f(1) is always 0 because the sequence of colors in its definition is empty.)
The permutation v ,v ,... ,v
is a beautiful permutation if and only if all the following
properties hold:
v = r.
For each i such that 1 ≤i < ∣T®∣, the parent of node v is node v
.
For any r such that 0 ≤r < N, the subtree T® is a beautiful subtree if and only if there exists a
beautiful permutation of the nodes in T®. Note that according to the definition every subtree
which consists of a single node is beautiful.
Consider the example tree above. It can be shown that the subtrees T(0) and T(3) of this tree are
not beautiful. The subtree T(14) is beautiful, as it consists of a single node. Below, we will show
that the subtree T(1) is also beautiful.
Consider the sequence of distinct integers [v ,v ,v ,v ,v ,v ,v ] = [1,4,5,12,13,6,14]. This
sequence is a permutation of the nodes in T(1). The figure below depicts this permutation. The
labels attached to the nodes are the indices at which those nodes appear in the permutation.
0
1
∣T®∣−1
i
1
2
i−1
0
1
∣T®∣−1
0
i
f(i)
0
1
2
3
4
5
6
beechtree (2 of 6)

We will now verify that this is a beautiful permutation.
v = 1.
f(1) = 0 since C[v ] = C[4] = 1 appears 0 times in the sequence [].
Correspondingly, the parent of v is v . That is, the parent of node 4 is node 1.
(Formally, P[4] = 1.)
f(2) = 0 since C[v ] = C[5] = 2 appears 0 times in the sequence [1].
Correspondingly, the parent of v is v . That is, the parent of 5 is 1.
f(3) = 1 since C[v ] = C[12] = 1 appears 1 time in the sequence [1,2].
Correspondingly, the parent of v is v . That is, the parent of 12 is 4.
f(4) = 1 since C[v ] = C[13] = 2 appears 1 time in the sequence [1,2,1].
Correspondingly, the parent of v is v . That is, the parent of 13 is 4.
f(5) = 0 since C[v ] = C[6] = 3 appears 0 times in the sequence [1,2,1,2].
Correspondingly, the parent of v is v . That is, the parent of 6 is 1.
f(6) = 2 since C[v ] = C[14] = 2 appears 2 times in the sequence [1,2,1,2,3].
Correspondingly, the parent of v is v . That is, the parent of 14 is 5.
As we could find a beautiful permutation of the nodes in T(1), the subtree T(1) is a beautiful
subtree.
Your task is to help Árpád decide for every subtree of Ős Vezér whether it is beautiful.
Implementation Details
You should implement the following procedure.
int[] beechtree(int N, int M, int[] P, int[] C)
N: the number of nodes in the tree.
0
1
1
0
2
2
0
3
3
1
4
4
1
5
5
0
6
6
2
beechtree (3 of 6)

M : the number of possible edge colors.
P, C: arrays of length N describing the edges of the tree.
This procedure should return an array b of length N. For each r such that 0 ≤r < N, b[r]
should be 1 if T® is beautiful, and 0 otherwise.
This procedure is called exactly once for each test case.
Examples
Example 1
Consider the following call:
beechtree(4, 2, [-1, 0, 0, 0], [0, 1, 1, 2])
The tree is displayed in the following figure:
T(1), T(2), and T(3) each consist of a single node and are therefore beautiful. T(0) is not
beautiful. Therefore, the procedure should return [0,1,1,1].
Example 2
Consider the following call:
beechtree(18, 3,
[-1, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 10, 11, 11],
[0, 1, 2, 3, 1, 2, 3, 1, 3, 3, 2, 1, 1, 2, 2, 1, 2, 3])
This example is illustrated in the task description above.
The procedure should return [0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1].
Example 3
Consider the following call:
beechtree (4 of 6)

beechtree(7, 2, [-1, 0, 1, 1, 0, 4, 5], [0, 1, 1, 2, 2, 1, 1])
This example is illustrated in the following figure.
T(0) is the only subtree that is not beautiful. The procedure should return [0,1,1,1,1,1,1].
Constraints
3 ≤N ≤200 000
2 ≤M ≤200 000
0 ≤P[i] < i (for each i such that 1 ≤i < N)
1 ≤C[i] ≤M (for each i such that 1 ≤i < N)
P[0] = −1 and C[0] = 0
Subtasks
1. (9 points) N ≤8 and M ≤500
2. (5 points) Edge i connects node i to node i −1. That is, for each i such that 1 ≤i < N,
P[i] = i −1.
3. (9 points) Each node other than node 0 is either connected to node 0, or is connected to a
node which is connected to node 0. That is, for each i such that 1 ≤i < N, either P[i] = 0
or P[P[i]] = 0.
4. (8 points) For each c such that 1 ≤c ≤M , there are at most two edges of color c.
5. (14 points) N ≤200 and M ≤500
6. (14 points) N ≤2 000 and M = 2
7. (12 points) N ≤2 000
8. (17 points) M = 2
9. (12 points) No additional constraints.
Sample Grader
The sample grader reads the input in the following format:
beechtree (5 of 6)

line 1: N M
line 2: P[0] P[1] ... P[N −1]
line 3: C[0] C[1] ... C[N −1]
Let b[0], b[1], ... denote the elements of the array returned by beechtree . The sample grader
prints your answer in a single line, in the following format:
line 1: b[0] b[1] ...
beechtree (6 of 6)

Input / Output on this judge

This is the IOI function-implementation task beechtree adapted to standard input / output. Instead of implementing the function, read its arguments from standard input and print the returned value(s) to standard output, exactly as the official grader below does (its internal anti-cheat checks have been removed). You may also simply submit the grader together with your own implementation of the function.

Function signature (beechtree.h):

#include <vector>

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C);

Reference I/O driver (official grader, sanitized):

#include "beechtree.h"
#include <cassert>
#include <cstdio>

int main()
{
    int N, M;
    assert(2 == scanf("%d %d", &N, &M));
    std::vector<int> P(N);
    for (int i = 0; i < N; ++i)
        assert(1 == scanf("%d", &P[i]));
    std::vector<int> C(N);
    for (int i = 0; i < N; ++i)
        assert(1 == scanf("%d", &C[i]));

    fclose(stdin);

    std::vector<int> res = beechtree(N, M, P, C);

    int n = res.size();
    for (int i = 0; i < n; ++i)
    {
        if (i > 0)
            printf(" ");
        printf("%d", res[i]);
    }
    printf("\n");
    fclose(stdout);

    return 0;
}

rip 작성

출처 IOI 2023