Broken Special Vertex

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <assert.h>

using namespace std;

struct Node {
    int i;
    int dist;
    Node *parent;
    vector<Node *> nexts;
};

int main() {
    int n;
    scanf("%d", &n);
    vector<Node> nodes(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a -= 1;
        b -= 1;
        nodes[a].nexts.push_back(&nodes[b]);
        nodes[b].nexts.push_back(&nodes[a]);
    }
    for (int i = 0; i < n; i++) {
        nodes[i].i = i;
    }
    queue<Node *> bfs;
    bfs.push(&nodes[0]);
    Node *prevpopped;
    while (bfs.size()) {
        for (Node *node : bfs.front()->nexts) {
            if (node != bfs.front()->parent) {
                node->parent = bfs.front();
                bfs.push(node);
            }
        }
        prevpopped = bfs.front();
        bfs.pop();
    }
    Node *u = prevpopped;
    u->parent = 0;
    u->dist = 0;
    bfs.push(u);
    while (bfs.size()) {
        for (Node *node : bfs.front()->nexts) {
            if (node != bfs.front()->parent) {
                node->dist = bfs.front()->dist + 1;
                node->parent = bfs.front();
                bfs.push(node);
            }
        }
        prevpopped = bfs.front();
        bfs.pop();
    }
    Node *v = prevpopped;
    int diameter = v->dist + 1;
    Node *root = v;
    for (int i = 0; i < diameter / 2; i++) {
        root = root->parent;
    }
    root->parent = 0;
    root->dist = 0;
    bfs.push(root);
    while (bfs.size()) {
        for (Node *node : bfs.front()->nexts) {
            node->dist = bfs.front()->dist + 1;
            node->parent = bfs.front();
            assert(find(node->nexts.begin(), node->nexts.end(), node->parent) != node->nexts.end());
            node->nexts.erase(find(node->nexts.begin(), node->nexts.end(), node->parent));
            bfs.push(node);
        }
        bfs.pop();
    }
    int feedback;
    Node *prevpreprocnode;
    Node *currnode = root;
    feedback = root->i;
    int queries = 0;
    bool hitbottom = false;
    vector<int> answers(n, -2);
    while (feedback != -1) {
        if (&nodes[feedback] != currnode->parent && !hitbottom) {
            currnode = &nodes[feedback];
            prevpreprocnode = currnode;
            while (currnode->nexts.size() == 1) {
                currnode = currnode->nexts[0];
            }

            if (currnode->nexts.size() == 0) {
                hitbottom = true;
                continue;
            }

            if (answers[currnode->i] == -2) {
                printf("%d\n", currnode->i + 1);
                fflush(stdout);
                scanf("%d", &feedback);
                feedback -= 1;
                answers[currnode->i] = feedback;
                assert(currnode->i != answers[currnode->i]);
                assert(feedback == -1 || currnode->i != answers[answers[currnode->i]]);
                queries++;
            } else {
                feedback = answers[currnode->i];
            }
        } else {
            assert(hitbottom || nodes[feedback].nexts.size() == 1);
            assert(hitbottom || (answers[currnode->i] == currnode->parent->i && answers[prevpreprocnode->parent->i] == prevpreprocnode->i));
            vector<Node *> nodechain;
            Node *tosearch = hitbottom ? currnode : currnode->parent;
            vector<bool> innodechain(n, false);
            while (tosearch != prevpreprocnode->parent) {
                nodechain.push_back(tosearch);
                innodechain[tosearch->i] = true;
                tosearch = tosearch->parent;
            }
            int rangebegin = 0;
            int rangeend = nodechain.size();
            while (true) {
                assert(rangebegin != rangeend);
                int tochecki = rangebegin + (rangeend - rangebegin) / 2;
                assert(tochecki != rangeend);
                if (answers[nodechain[tochecki]->i] == -2) {
                    printf("%d\n", nodechain[tochecki]->i + 1);
                    fflush(stdout);
                    scanf("%d", &feedback);
                    feedback -= 1;
                    answers[nodechain[tochecki]->i] = feedback;
                    assert(currnode->i != answers[currnode->i]);
                    assert(feedback == -1 || currnode->i != answers[answers[currnode->i]]);
                    queries++;
                } else {
                    feedback = answers[nodechain[tochecki]->i];
                }
                if (feedback == -1) {
                    return 0;
                } else if (tochecki - 1 >= rangebegin && feedback == nodechain[tochecki - 1]->i) {
                    rangeend = tochecki;
                } else if (tochecki + 1 < rangeend && feedback == nodechain[tochecki + 1]->i) {
                    rangebegin = tochecki + 1;
                } else {
                    //assert(innodechain[feedback] || innodechain[nodes[feedback].parent->i]);
                }
            }
        }
    }
    return 0;
}