C++ 代码优化：降低时间复杂度

这段代码实现了一个树形结构的遍历和最大权值匹配算法。为了降低代码的时间复杂度，可以采取以下几个优化措施：

优化 dfs 函数： 在 dfs 函数中，每次递归调用都会将 u->id 放入 tic 数组中，然后在 calcdp 函数中进行预处理。可以在 dfs 函数中直接进行预处理，将 u->id 存入 dp 数组，避免了 tic 数组的使用。

void dfs(Node *u, int dep = 1) {
  dp[0][++p] = u->id;  // 直接将 u->id 存入 dp 数组
  u->firapp = p;
  u->dep = dep;
  for (Edge *e = u->fir; e; e = e->nxt) {
    dfs(e->to, dep + 1);
    dp[0][++p] = u->id; // 将 u->id 再次存入 dp 数组
  }
}

优化 calcdp 函数： 在 calcdp 函数中，每次比较 dep 大小时都会调用 cmp 函数，可以将 cmp 函数的功能直接集成到 calcdp 函数中，避免了函数调用的开销。

void calcdp(int n) {
  for (int i = 1; i <= n; ++i) dp[0][i] = tic[i];
  for (int k = 1; k <= 18; ++k) {
    for (int i = 1; i + (1 << k) - 1 <= n; ++i) {
      if (no[dp[k - 1][i]].dep < no[dp[k - 1][i + (1 << (k - 1))]].dep) {
        dp[k][i] = dp[k - 1][i];
      } else {
        dp[k][i] = dp[k - 1][i + (1 << (k - 1))];
      }
    }
  }
}

优化 lca 函数： 在 lca 函数中，使用了 log 函数和 pow 函数来计算 k 的值，可以使用位运算的方式来代替。

int lca(int u, int v) {
  if (no[u].firapp > no[v].firapp) std::swap(u, v);
  int k = 0;
  while ((1 << (k + 1)) <= no[v].firapp - no[u].firapp + 1) {
    k++;
  }
  return cmp(dp[k][no[u].firapp], dp[k][no[v].firapp + 1 - (1 << k)]);
}

优化主函数：
- 使用快速排序代替优先队列对节点进行排序。
- 使用两个指针来遍历两个子树，避免了优先队列的操作。
- 使用一个数组来存储每个节点的子节点个数，避免了对度数的判断。
- 直接在 dfs 函数中处理父节点，避免了对父节点的判断。

通过以上优化措施，可以显著降低代码的时间复杂度。需要注意的是，优化后的代码需要进行充分的测试，确保代码的正确性和稳定性。