classSolution { public: intmaxDepth(TreeNode* root){ if (!root) return0; queue<TreeNode*> q; q.push(root); int ans = 0; while (!q.empty()) { int len = q.size(); // 分层遍历 while (len --) { TreeNode* t = q.front(); q.pop(); if (t->right) q.push(t->right); if (t->left) q.push(t->left); } ans ++; } return ans; } };
classSolution { public: intminDepth(TreeNode* root){ if (!root) return0; queue<TreeNode*> q; q.push(root); int ans = 0; while (!q.empty()) { ans ++; int len = q.size(); while (len --) { TreeNode* t = q.front(); q.pop(); if (!t->left && !t->right) return ans; if (t->left) q.push(t->left); if (t->right) q.push(t->right); } } return ans; } };
constint N = 10010, M = N * 2; int n; int h[N], e[M], ne[M], w[M], idx; int ans;
voidadd(int a, int b, int c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; }
intdfs(int u, int father){ int dist = 0; // 表示当前节点到叶子节点的最长路径(与d1含义一致,可省略) int d1 = 0, d2 = 0; // 保存到当前节点到叶子节点的最长路径和次最长路径 for (int i = h[u]; ~i; i = ne[i]) { int t = e[i]; if (t == father) continue; int d = dfs(t, u) + w[i]; // 获取该子树的最长路径 dist = max(dist, d); // 更新当前节点到叶子节点的最长路径和次最长路径 if (d >= d1) d2 = d1, d1 = d; elseif (d > d2) d2 = d; } ans = max(ans, d1 + d2); return dist; }
intmain(){ memset(h, -1, sizeof h); cin >> n; int a, b, c; for (int i = 0; i < n - 1; i ++) { scanf("%d%d%d", &a, &b, &c); add(a, b, c), add(b, a, c); } dfs(1, -1); cout << ans << endl; return0; }
classSolution { public: int res = INT_MIN; intmaxPathSum(TreeNode* root){ dfs(root); return res; }
intdfs(TreeNode* root){ if (!root) return0; int dist = 0; int left = dfs(root->left), right = dfs(root->right); dist = max(dist, max(left, right) + root->val); res = max(res, left + right + root->val); return dist; } };
constint N = 100010, M = 2 * N; int n, x, y; int h[N], e[M], ne[M], idx;
voidadd(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }
intdfs(int u, int father){ int dist = 0; // 遍历该节点的所有子节点 for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == father) continue; dist = max(dist, dfs(j, u)); } return dist + 1; }
intmain(){ memset(h, -1, sizeof h); cin >> n; int p; for (int i = 1; i < n; i ++) { scanf("%d", &p); add(i + 1, p), add(p, i + 1); } cin >> x >> y; int x_dist = dfs(x, y) - 1; // 以x为根的子树最长路径 int y_dist = dfs(y, x) - 1; // 以y为根的子树最长路径 cout << x_dist + y_dist + 1 << endl; // 加上x,y之间的路径1 return0; }