优化树形结构最大权值路径问题：时间复杂度降低技巧

#include <bits/stdc++.h> #define ll long long const int kN = 2e5+10; struct Node { struct Edge *fir; int dep, firapp, id; bool flag; }no[kN]; struct Edge { Node *to; Edge *nxt; }pool[kN], *til = pool; void add(Node *u, Node *v) { (++til)->to = v; til->nxt = u->fir; u->fir = til; } int tic[kN << 1], p = 0; void dfs(Node *u, int dep = 1) { tic[++p] = u->id; u->firapp = p; u->dep = dep; for (Edge e = u->fir; e; e = e->nxt) { dfs(e->to, dep+1); tic[++p] = u->id; } } int dp[20][kN << 1]; int cmp(int a, int b) { if (no[a].dep < no[b].dep) return a; return b; } 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) dp[k][i] = cmp(dp[k-1][i], dp[k-1][i+(1 << (k-1))]); } struct ST { ll m; int id; }a[kN]; bool cmp2(ST a, ST b) { return a.m > b.m; } int lca(int u, int v) { if (no[u].firapp > no[v].firapp) std::swap(u, v); int k = (int)(log(no[v].firapp-no[u].firapp+1)/log(2)); return cmp(dp[k][no[u].firapp], dp[k][no[v].firapp+1-(1 << k)]); } int flist[kN], ft; int du[kN], fa[kN]; std::priority_queue p1, p2; int main() { //freopen("spring.in", "r", stdin); //freopen("spring.out", "w", stdout); int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%lld", &a[i].m); for (int i = 1; i <= n; ++i) { a[i].id = i; no[i].id = i; no[i].flag = false; } bool tflag = true; for (int i = 2; i <= n; ++i) { int x; scanf("%d", &x); du[x]++; if ((x == 1 && du[x]>2) || (x != 1 && du[x] > 1)) tflag = false; fa[i] = x; add(&no[x], &no[i]); } if (tflag) { ll ret = a[1].m; int ind = -1; for (int i = 1; i <= n; ++i) if (du[i] == 0) {ind = i; break;} du[ind] = 2; while (fa[ind] != 0) { p1.push(a[ind].m); ind = fa[ind]; } ind = -1; for (int i = 1; i <= n; ++i) if (du[i] == 0) {ind = i; break;} if (ind != -1) { while (fa[ind] != 0) { p2.push(a[ind].m); ind = fa[ind]; } } while (!p1.empty() || !p2.empty()) { ll x = 0ll, y = 0ll; if (!p1.empty()) { x = p1.top(); p1.pop(); } if (!p2.empty()) { y = p2.top(); p2.pop(); } ret += std::max(x, y); } std::cout << ret << std::endl; return 0; } dfs(&no[1]); // for (int i = 1; i <= p; ++i) printf("%d ", tic[i]); // printf("\n"); calcdp(2n-1); std::sort(a+1, a+n+1, cmp2); ll ret = 0; for (int i = 1; i <= n; ++i) { if (no[a[i].id].flag) continue; ret = ret + a[i].m; ft = 0; flist[++ft] = a[i].id; for (int j = i+1; j <= n; ++j) if (!no[a[j].id].flag){ bool flag = true; for (int k = 1; k <= ft; ++k) { int lc = lca(flist[k], a[j].id); if (lc == a[j].id || lc == flist[k]) { flag = false; break; } } if (flag) { no[a[j].id].flag = true; flist[++ft] = a[j].id; } } } std::cout << ret << std::endl; return 0; }

如何降低这段代码的时间复杂度内容：要降低这段代码的时间复杂度，可以考虑以下优化措施：

使用邻接表存储图的边，而不是邻接矩阵。邻接表可以降低图的存储空间复杂度，并且可以更高效地遍历图的边。
使用深度优先搜索（DFS）遍历图，而不是广度优先搜索（BFS）。DFS可以更快地遍历整个图，并且可以在遍历时计算节点的深度和第一次出现的位置。
使用倍增法预处理最近公共祖先（LCA）信息。通过预处理得到每个节点的2^k级祖先，可以快速计算任意两个节点的LCA。
使用堆（优先队列）来维护每个节点的权值。通过使用堆，可以在O(logn)时间内找到最大的权值，并且可以在O(logn)时间内插入新的权值。
使用贪心算法来选择节点。通过贪心策略，可以选择权值最大的节点，并且保证选择的节点不会与已选择的节点形成环。

通过以上优化措施，可以降低代码的时间复杂度，并提高程序的运行效率。