[코드포스 Practice10] E. Military Problem (미완)

In this problem you will have to help Berland army with organizing their command delivery system.

이 문제에서 너는 Berland 군대의 명령전달 시스템을 구성하는 것을 도와야 할것이다.

There are n officers in Berland army. The first officer is the commander of the army, and he does not have any superiors. Every other officer has exactly one direct superior. If officer a is the direct superior of officer b, then we also can say that officer b is a direct subordinate of officer a.

Berland 군대에는 n명의 장교가 있다. 첫번째 장교는 군대의 사령관이고 그는 상사가 없다. 다른 모든 장교들은 정확히 한 명의 직속 상관이 있다. 만약 a가 b의 직속 상관이라면 우리는 또한 b가 a의 직속 부하직원이라 말할 수 있다.

Officer x is considered to be a subordinate (direct or indirect) of officer y if one of the following conditions holds:

만약 다음 조건 중 하나가 충족되는 경우 장교 x는 (직속이든 아니든) y의 부하직원이라 여겨진다.

 

• officer y is the direct superior of officer x;
• the direct superior of officer x is a subordinate of officer y.

y는 x의 직속 상관 일 때

x의 직속 상관이 y의 부하직원일 때

 

For example, on the picture below the subordinates of the officer 3 are: 5,6,7,8,9.

예를들어, 아래 사진에서 3의 부하직원은 5,6,7,8,9이다.

The structure of Berland army is organized in such a way that every officer, except for the commander, is a subordinate of the commander of the army.

Berland 군대의 구조는 사령관을 제외한 모든 장교들이 사령관의 부하직원인 방식으로 조직되었다.

Formally, let's represent Berland army as a tree consisting of n vertices, in which vertex u corresponds to officer u. The parent of vertex u corresponds to the direct superior of officer u. The root (which has index 1) corresponds to the commander of the army.

형식적으로 Berland 군대를 n개의 vertex를 포함하는 트리로 표현해보자, vertex u는

Berland War Ministry has ordered you to give answers on q queries, the i-th query is given as (ui,ki), where ui is some officer, and ki is a positive integer.

To process the i-th query imagine how a command from ui spreads to the subordinates of ui. Typical DFS (depth first search) algorithm is used here.

Suppose the current officer is a and he spreads a command. Officer a chooses b — one of his direct subordinates (i.e. a child in the tree) who has not received this command yet. If there are many such direct subordinates, then a chooses the one having minimal index. Officer a gives a command to officer b. Afterwards, b uses exactly the same algorithm to spread the command to its subtree. After b finishes spreading the command, officer a chooses the next direct subordinate again (using the same strategy). When officer a cannot choose any direct subordinate who still hasn't received this command, officer a finishes spreading the command.

---

번역은 다 안 했지만 뭘 원하는지 알겠다

 

 

아 근데 2시간 여유시간이 지금 밖에 없어서 지금 11번째 코포를 먼저 풀어놔야겠다. 코포 풀고 -> 다시 e번 풀고 -> 코포 정리하고 -> 내일 백준풀고하면 될듯

 

#include <iostream>
#include <vector>
using namespace std;


int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    
    vector<int> parent(n);
    vector<int> child[n];
    
    for(int i = 2; i <= n; i++){
        scanf("%d", &parent[i]);
        child[parent[i]].push_back(i);
    }
    
    
}