human
Alice and Bob are well-known for sending messages to each other. This time you have a rooted tree with Bob standing in the root node and copies of Alice standing in each of the other vertices. The root node has number 0, the rest are numbered 1 through n.

At some moments of time some copies of Alice want to send a message to Bob and receive an answer. We will call this copy the initiator. The process of sending a message contains several steps: 

  * The initiator sends the message to the person standing in the parent node and begins waiting for the answer. 
  * When some copy of Alice receives a message from some of her children nodes, she sends the message to the person standing in the parent node and begins waiting for the answer. 
  * When Bob receives a message from some of his child nodes, he immediately sends the answer to the child node where the message came from. 
  * When some copy of Alice (except for initiator) receives an answer she is waiting for, she immediately sends it to the child vertex where the message came from. 
  * When the initiator receives the answer she is waiting for, she doesn't send it to anybody. 
  * There is a special case: a copy of Alice can't wait for two answers at the same time, so if some copy of Alice receives a message from her child node while she already waits for some answer, she rejects the message and sends a message saying this back to the child node where the message came from. Then the copy of Alice in the child vertex processes this answer as if it was from Bob. 
  * The process of sending a message to a parent node or to a child node is instant but a receiver (a parent or a child) gets a message after 1 second. 


If some copy of Alice receives several messages from child nodes at the same moment while she isn't waiting for an answer, she processes the message from the initiator with the smallest number and rejects all the rest. If some copy of Alice receives messages from children nodes and also receives the answer she is waiting for at the same instant,...
assistant
#Here is the Python program you requested.

#include <bits/stdc++.h>
using namespace std;
using namespace rel_ops;
using ll = int64_t;
using Pii = pair<int, int>;
using ull = uint64_t;
using Vi = vector<int>;
void run();
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  run();
  return 0;
}
int uplg(int n) { return 32 - __builtin_clz(n); }
int uplg(ll n) { return 64 - __builtin_clzll(n); }
struct SegmentTree {
  using T = int;
  static constexpr T ID = INT_MIN;
  struct Node {
    T extra{ID};
    T great{INT_MIN};
    void init(T first, int) { great = first; }
    void merge(const Node& R) { great = max(great, R.great); }
    T apply(T first, int begin, int size) {
      extra = max(extra, first);
      great = max(great, first + (begin + size - 1) * 2);
      return first;
    }
  };
  vector<Node> V;
  int len;
  SegmentTree(int n = 0, T def = ID) { init(n, def); }
  void init(int n, T def) {
    for (len = 1; len < n; len *= 2)
      ;
    V.assign(len * 2, {});
    for (int i = (len); i < (len + n); i++) V[i].init(def, 1);
    for (int i = len - 1; i > 0; i--) update(i);
  }
  int getChild(int i, int j) { return i * 2 + j; }
  int L(int i) { return getChild(i, 0); }
  int R(int i) { return getChild(i, 1); }
  void update(int i) {
    int a = L(i), b = R(i);
    V[i] = {};
    V[i].merge(V[a]);
    V[i].merge(V[b]);
  }
  void push(int i, int begin, int size) {
    int e = V[i].extra;
    if (e != ID) {
      e = V[L(i)].apply(e, begin, size / 2);
      V[R(i)].apply(e, begin + size / 2, size / 2);
      V[i].extra = ID;
    }
  }
  T modify(int vBegin, int vEnd, T first, int i = 1, int begin = 0,
           int end = -1) {
    if (end < 0) end = len;
    if (vEnd <= begin || end <= vBegin) return first;
    if (vBegin <= begin && end <= vEnd) {
      return V[i].apply(first, begin, end - begin);
    }
    int mid = (begin + end) / 2;
    push(i, begin, end - begin);
    first = modify(vBegin, vEnd, first, L(i), begin, mid);
    first = modify(vBegin, vEnd, first, R(i), mid, end);
    update(i);
    return...