tree_search (EJOI contest)
Time limit: 1 seconds | Memory limit: 2024 MB | Task type: interactive
Algorithms: centroid decomposition, divide and conquer, binary search, tree

# Tree Search

You are given a rooted binary tree consisting of *N* vertices. The vertices are numbered from 1 to *N*, the root is the vertex number 1. Each of the other vertices has a single parent in the tree. The tree is binary, i.e., each vertex can be a parent of at most two other vertices.

One of the vertices is special. You are trying to guess it. You can ask questions of the following kind: "Is the special vertex in the subtree of vertex *x*?" A node *y* is in the subtree of vertex *x* if and only if the shortest path between *y* and 1 goes through vertex *x*. Note that vertex *x* is also in its own subtree.

You are allowed to ask this question at most 35 times. After that, you should report your guess.

## Implementation Details

You should implement the following procedure:

```cpp
int solve(int N, std::vector < int > p)
```

*   *N*: the number of vertices
*   *p* contains exactly *N* − 1 elements that describe the tree: the vertex *p*[*i*] (where 1 ≤ *p*[*i*] ≤ *i* + 1) is the parent of the vertex *i* + 2 for each 0 ≤ *i* ≤ *N* − 2
*   No element in *p* appears more than twice.
*   This procedure should return the number of the special vertex.
*   This procedure is called exactly once.

The above procedure can make calls to the following procedure:

```cpp
int ask(int x)
```

*   *x*: the number of the vertex
*   1 ≤ *x* ≤ *N*
*   returns 1 if the special vertex is in the subtree of *x* and 0 otherwise

## Example

Consider the following call:

```cpp
solve(5, [1, 1, 2, 4])
```

The tree consists of the edges (1,2), (1,3), (2,4), and (4,5).

![](_page_1_Figure_2.jpeg)

Your program made a call

```cpp
ask(4)
```

which returned 1. After that, your program made a call

```cpp
ask(5)
```

which returned 0.

Your program concluded that vertex 4 is special and returned 4.

## Constraints

*   2 ≤ *N* ≤ 100 000

## Subtasks

1.  (20 points) *N* ≤ 35
2.  (30 points) *p*[*i*] = *i* + 1 for each 0 ≤ *i* ≤ *N* − 2
3.  (15 points) *p*[*i*] = ⌊*i*/2⌋ + 1 for each 0 ≤ *i* ≤ *N* − 2
4.  (35 points) No additional constraints.

## Sample Grader

The sample grader reads the input in the following format:

*   line 1: *N*
*   line 2: *p*[0], *p*[1], ..., *p*[*N* − 2]

The sample grader outputs each question in the following format:

*   line 1: `? x`

The sample grader reads each answer in the following format:

*   line 1: *y*

The sample grader outputs the guess in the following format:

*   line 1: `! x`

Starter code:
stub.h: #include <bits/stdc++.h>

int solve(int N, std::vector<int> p);

bool ask(int x) {
	printf("? %d ", x);
	fflush(stdout);
	int res;
	int ignore = scanf("%d", &res);
	return res;
}

int main() {
    int n, a, b;
	int ignore = scanf("%d", &n);
    std::vector<int>p(n-1);

	for(int i=0;i<n-1;i++){
        ignore = scanf("%d", &p[i]);
	}

	int res = solve(n, p);
	printf("! %d ", res);
	fflush(stdout);
}


stub.cpp: #include <bits/stdc++.h>

int solve(int N, std::vector<int> p);

bool ask(int x) {
	printf("? %d ", x);
	fflush(stdout);
	int res;
	int ignore = scanf("%d", &res);
	return res;
}

int main() {
    int n, a, b;
	int ignore = scanf("%d", &n);
    std::vector<int>p(n-1);

	for(int i=0;i<n-1;i++){
        ignore = scanf("%d", &p[i]);
	}

	int res = solve(n, p);
	printf("! %d ", res);
	fflush(stdout);
}


interactor.cpp: #include<bits/stdc++.h>
#include"testlib.h" 
using namespace std;

const int limit = 35;

vector<array<int, 2> > questions;
int root = 1;
vector<int> v[100005];
int in_t[100005], out_t[100005], t;
int fx[100005], sz[100005], par[100005];
int n, ch;

void dfs(int ver, int p){
    par[ver] = p;
    in_t[ver] = t++;
    for(int to: v[ver]){
        if(to != p)
            dfs(to, ver);
    }
    out_t[ver] = t;
}

void measure(int ver, int par){
    sz[ver] = 1;
    for(int to: v[ver]){
        if(to != par && !fx[to]){
            measure(to, ver);
            sz[ver] += sz[to];
        }
    }
}

bool check_par(int p, int ch){
    return in_t[p] <= in_t[ch] && out_t[p] >= out_t[ch];
}

bool check_inside(int ver){
    for(array<int, 2> q: questions){
        if (check_par(q[0], ver) != q[1])
            return false;
    }
    return true;
}

bool decide(int ver){
    if(!check_inside(ver)){
        return check_par(ver, root);
    }
    fill(sz + 1, sz + n + 1, 0);
    measure(root, 0);
    if(sz[ver] >= sz[root]/2){
        root = ver;
        fx[par[ver]] = 1;
        return true;
    }
    else{
        fx[ver] = 1;
        return false;
    }
}

bool check_ans(int ans){
    if(ans<0 || ans>n)
    	return false;
    if(ch != -1){
        return ans == ch;
    }
    if(ans != root)
        return false;
    fill(sz + 1, sz + n + 1, 0);
    measure(root, 0);
    if(sz[root] != 1)
        return false;
    return true;
}

int main(int argc, char **argv){

    registerInteraction(argc, argv);

    n = inf.readInt(), ch = inf.readInt();

    cout << n << endl;

    for(int i=0;i<n-1;i++){
        int a = inf.readInt();
        cout << a << endl;
        v[a].push_back(i+2);
        v[i+2].push_back(a);
    }

    dfs(1, 0);

    int asked = 0;
    while(1){
        char c;
        if(!(cin >> c)){
            quitf(_wa, "Presentation error.");
            return 0;
        }
        if(c == '?'){
            asked++;
            if (asked > limit){
                quitf(_wa, "translate:wrong");
                return 0;
            }
            int ver;
            if(!(cin >> ver)){
                quitf(_wa, "Presentation error.");
                return 0;
            }
            if(ver<0 || ver>n){
                quitf(_wa, "Presentation error.");
                return 0;
            }
            if(ch==-1){
                int ret = decide(ver);
                questions.push_back({ver, ret});
                cout << ret << endl;
            } else {
                int ret = check_par(ver, ch);
                cout << ret << endl;
            }
        } else
        if (c == '!'){
            int g;
            if(!(cin >> g)){
                quitf(_wa, "Presentation error.");
                return 0;
            }
            if (check_ans(g)){
                quitf(_ok, "translate:success");
                return 0;
            } else {
                quitf(_wa, "translate:wrong");
                return 0;
            }
            break;
        } else {
            quitf(_wa, "Presentation error.");
            return 0;
        }
    }

    quitf(_wa, "translate:wrong");
   return 0;
}

checker.cpp: #include<bits/stdc++.h>

using namespace std;

ifstream inp;
ofstream out;
const int limit = 35;

vector<array<int, 2> > questions;
int root = 1;
vector<int> v[100005];
int in_t[100005], out_t[100005], t;
int fx[100005], sz[100005], par[100005];
int n, ch;

void dfs(int ver, int p){
    par[ver] = p;
    in_t[ver] = t++;
    for(int to: v[ver]){
        if(to != p)
            dfs(to, ver);
    }
    out_t[ver] = t;
}

void measure(int ver, int par){
    sz[ver] = 1;
    for(int to: v[ver]){
        if(to != par && !fx[to]){
            measure(to, ver);
            sz[ver] += sz[to];
        }
    }
}

bool check_par(int p, int ch){
    return in_t[p] <= in_t[ch] && out_t[p] >= out_t[ch];
}

bool check_inside(int ver){
    for(array<int, 2> q: questions){
        if (check_par(q[0], ver) != q[1])
            return false;
    }
    return true;
}

bool decide(int ver){
    if(!check_inside(ver)){
        return check_par(ver, root);
    }
    fill(sz + 1, sz + n + 1, 0);
    measure(root, 0);
    if(sz[ver] >= sz[root]/2){
        root = ver;
        fx[par[ver]] = 1;
        return true;
    }
    else{
        fx[ver] = 1;
        return false;
    }
}

bool check_ans(int ans){
    if(ans<0 || ans>n)
    	return false;
    if(ch != -1){
        return ans == ch;
    }
    if(ans != root)
        return false;
    fill(sz + 1, sz + n + 1, 0);
    measure(root, 0);
    if(sz[root] != 1)
        return false;
    return true;
}

int main(int argc, char **argv){


    out.open(argv[2]);
    inp.open(argv[1]);

    int ignore;
    ignore = scanf("%d %d", &n, &ch);

    out << n << endl;

    for(int i=0;i<n-1;i++){
        int a;
        ignore = scanf("%d", &a);
        out << a << endl;
        v[a].push_back(i+2);
        v[i+2].push_back(a);
    }

    dfs(1, 0);

    int asked = 0;
    while(1){
        char c;
        if(!(inp >> c)){
            cout << "0.0" << endl;
            fprintf(stderr, "Presentation error.");
            fflush(stderr);
            return 0;
        }
        if(c == '?'){
            asked++;
            if (asked > limit){
                cout << "0.0" << endl;
                fprintf(stderr, "translate:wrong");
                fflush(stderr);
                return 0;
            }
            int ver;
            if(!(inp >> ver)){
                cout << "0.0" << endl;
                fprintf(stderr, "Presentation error.");
                fflush(stderr);
                return 0;
            }
            if(ver<0 || ver>n){
                cout << "0.0" << endl;
                fprintf(stderr, "Presentation error.");
                fflush(stderr);
                return 0;
            }
            if(ch==-1){
                int ret = decide(ver);
                questions.push_back({ver, ret});
                out << ret << endl;
            } else {
                int ret = check_par(ver, ch);
                out << ret << endl;
            }
        } else
        if (c == '!'){
            int g;
            if(!(inp >> g)){
                cout << "0.0" << endl;
                fprintf(stderr, "Presentation error.");
                fflush(stderr);
                return 0;
            }
            if (check_ans(g)){
                cout << "1.0" << endl;
                fprintf(stderr, "translate:success");
                fflush(stderr);
                return 0;
            } else {
                cout << "0.0" << endl;
                fprintf(stderr, "translate:wrong");
                fflush(stderr);
                return 0;
            }
            break;
        } else {
            cout << "0.0" << endl;
            fprintf(stderr, "Presentation error.");
            fflush(stderr);
            return 0;
        }
    }

    cout << "0.0" << endl;
    fprintf(stderr, "translate:wrong");
    fflush(stderr);
   return 0;
}

search.cpp: #include "stub.h"

int solve(int N, std::vector<int> p){
	bool b = ask(1);
    return 1;
}


Grader code:
stub.h: #include <bits/stdc++.h>

int solve(int N, std::vector<int> p);

bool ask(int x) {
	printf("? %d ", x);
	fflush(stdout);
	int res;
	int ignore = scanf("%d", &res);
	return res;
}

int main() {
    int n, a, b;
	int ignore = scanf("%d", &n);
    std::vector<int>p(n-1);

	for(int i=0;i<n-1;i++){
        ignore = scanf("%d", &p[i]);
	}

	int res = solve(n, p);
	printf("! %d ", res);
	fflush(stdout);
}


stub.cpp: #include <bits/stdc++.h>

int solve(int N, std::vector<int> p);

bool ask(int x) {
	printf("? %d ", x);
	fflush(stdout);
	int res;
	int ignore = scanf("%d", &res);
	return res;
}

int main() {
    int n, a, b;
	int ignore = scanf("%d", &n);
    std::vector<int>p(n-1);

	for(int i=0;i<n-1;i++){
        ignore = scanf("%d", &p[i]);
	}

	int res = solve(n, p);
	printf("! %d ", res);
	fflush(stdout);
}


interactor.cpp: #include<bits/stdc++.h>
#include"testlib.h" 
using namespace std;

const int limit = 35;

vector<array<int, 2> > questions;
int root = 1;
vector<int> v[100005];
int in_t[100005], out_t[100005], t;
int fx[100005], sz[100005], par[100005];
int n, ch;

void dfs(int ver, int p){
    par[ver] = p;
    in_t[ver] = t++;
    for(int to: v[ver]){
        if(to != p)
            dfs(to, ver);
    }
    out_t[ver] = t;
}

void measure(int ver, int par){
    sz[ver] = 1;
    for(int to: v[ver]){
        if(to != par && !fx[to]){
            measure(to, ver);
            sz[ver] += sz[to];
        }
    }
}

bool check_par(int p, int ch){
    return in_t[p] <= in_t[ch] && out_t[p] >= out_t[ch];
}

bool check_inside(int ver){
    for(array<int, 2> q: questions){
        if (check_par(q[0], ver) != q[1])
            return false;
    }
    return true;
}

bool decide(int ver){
    if(!check_inside(ver)){
        return check_par(ver, root);
    }
    fill(sz + 1, sz + n + 1, 0);
    measure(root, 0);
    if(sz[ver] >= sz[root]/2){
        root = ver;
        fx[par[ver]] = 1;
        return true;
    }
    else{
        fx[ver] = 1;
        return false;
    }
}

bool check_ans(int ans){
    if(ans<0 || ans>n)
    	return false;
    if(ch != -1){
        return ans == ch;
    }
    if(ans != root)
        return false;
    fill(sz + 1, sz + n + 1, 0);
    measure(root, 0);
    if(sz[root] != 1)
        return false;
    return true;
}

int main(int argc, char **argv){

    registerInteraction(argc, argv);

    n = inf.readInt(), ch = inf.readInt();

    cout << n << endl;

    for(int i=0;i<n-1;i++){
        int a = inf.readInt();
        cout << a << endl;
        v[a].push_back(i+2);
        v[i+2].push_back(a);
    }

    dfs(1, 0);

    int asked = 0;
    while(1){
        char c;
        if(!(cin >> c)){
            quitf(_wa, "Presentation error.");
            return 0;
        }
        if(c == '?'){
            asked++;
            if (asked > limit){
                quitf(_wa, "translate:wrong");
                return 0;
            }
            int ver;
            if(!(cin >> ver)){
                quitf(_wa, "Presentation error.");
                return 0;
            }
            if(ver<0 || ver>n){
                quitf(_wa, "Presentation error.");
                return 0;
            }
            if(ch==-1){
                int ret = decide(ver);
                questions.push_back({ver, ret});
                cout << ret << endl;
            } else {
                int ret = check_par(ver, ch);
                cout << ret << endl;
            }
        } else
        if (c == '!'){
            int g;
            if(!(cin >> g)){
                quitf(_wa, "Presentation error.");
                return 0;
            }
            if (check_ans(g)){
                quitf(_ok, "translate:success");
                return 0;
            } else {
                quitf(_wa, "translate:wrong");
                return 0;
            }
            break;
        } else {
            quitf(_wa, "Presentation error.");
            return 0;
        }
    }

    quitf(_wa, "translate:wrong");
   return 0;
}


Setup script:

Evaluation script: