Brute Force Algorithm (Time Limit Exceeded)

TODO: 争取早日AC !!!

#pragma GCC optimize ("Ofast")

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

using namespace std;

const int kMod = 201314;
const int N = 5E4 + 10;

struct Node {
  int val; // 节点的编号
  vector<Node*> children;
  Node(int _val) : val(_val) {};
  ~Node() {};
};

int n, q;

vector<Node*> repos(N, nullptr);

// dubug helper function
// N 叉树的前序遍历
void preOrder(Node* node) {
  printf("%d ", node->val);
  for (const auto& child : node->children)
    preOrder(child);
}

// 在N叉树上求一个节点深度 (1-based) 根节点的深度为1
int depth(Node* root, int val) {

  assert(root);

  queue<Node*> q{{root}};
  int level = 1;
  while (not q.empty()) {
    size_t sz = q.size();
    while (sz--) {
      const auto cur = q.front(); q.pop();
      if (cur->val == val) return level;
      for (const auto& child : cur->children)
        q.emplace(child);
    }
    ++level;
  }
  return -1;
}

// 在N叉树上求两个节点的LCA （Lowest Common Ancestor）
Node* lowestCommonAncestor(Node* root, int p, int q) {
  // 结点自已可以是自已的袓先
  if (p == q) return repos[p];
  if (root->val == p || root->val == q) return root;

  bool found_1 = false, found_2 = false;
  Node *node1 = nullptr, *node2 = nullptr;
  for (const auto& child : root->children) {
    Node* node = lowestCommonAncestor(child, p, q);
    if (node) {
      if (!found_1) {
        node1 = node;
        found_1 = true;
      } else {
        node2 = node;
        found_2 = true;
      }
    }
    if (found_1 && found_2) break; // 无需继续再找了
  }
  return node1 && node2 ? root : node1 ? node1 : node2;
}

int main(void) {
  scanf("%d %d", &n, &q);

  repos[0] = new Node(0);
  for (int i = 1; i < n; ++i) {
    int p;
    scanf("%d", &p);

    repos[i] = new Node(i);
    Node* parent = repos[p];
    if (!parent) {
      parent = new Node(p);
      repos[p] = parent;
    }
    parent->children.emplace_back(repos[i]);
  }

  // unit test
  // preOrder(repos.at(0));

  // assert( depth(repos.at(0), 0) == 1 );
  // assert( depth(repos.at(0), 1) == 2 );
  // assert( depth(repos.at(0), 2) == 2 );
  // assert( depth(repos.at(0), 3) == 3 );
  // assert( depth(repos.at(0), 4) == 3 );

  // assert( lowestCommonAncestor(repos.at(0), 1, 3)->val == 1 );
  // assert( lowestCommonAncestor(repos.at(0), 2, 3)->val == 0 );
  // assert( lowestCommonAncestor(repos.at(0), 3, 3)->val == 3 );
  // assert( lowestCommonAncestor(repos.at(0), 4, 3)->val == 1 );

  while (q--) {
    int l, r, z;
    scanf("%d %d %d", &l, &r, &z);
    long sum = 0;
    for (int i = l; i <= r; ++i) {
      auto lca = lowestCommonAncestor(repos[0], i, z);
      if (lca) sum += depth(repos[0], lca->val);
    }
    printf("%d\n", sum % kMod);
  }
}