G.登山小分队(暴力&dfs)

G.登山小分队(暴力&dfs)

G.登山小分队(暴力&dfs)

开vector维护到达每个顶点的人的时间。每次排序，更新相同的时间的然后向上合并即可。

#include #define int long longusing namespace std;const int N = 5e5 + 5;int n, u, v, x;vector vec[N], g[N];void dfs(int x, int fa) { int flag = 1; for (auto y : vec[x]) { if (y == fa) continue; dfs(y, x); flag = 0; } if (flag) //叶 g[x].push_back(0); sort(g[x].begin(), g[x].end()); if (x != 1) { int len = g[x].size(); for (int i = 1; i < len; i++) //当前结点 处理到达时间相同的 g[x][i] = max(g[x][i], g[x][i - 1] + 1); for (auto v : g[x]) //+1递交给父结点 g[fa].push_back(v + 1); }}signed main() { cin >> n; for (int i = 1; i < n; i++) { cin >> u >> v; vec[u].push_back(v); vec[v].push_back(u); } dfs(1, -1); // for (int i = 1; i <= n; i++) { // cout << i << ":" << endl; // for (auto x : g[i]) // cout << x << " "; // cout << endl; // } cout << g[1][g[1].size() - 1]; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。