Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define sz(v) (int)v.size()
- #define all(v) v.begin(), v.end()
- #define pb emplace_back
- #define mp make_pair
- #define debug(x) cout << #x << " = " << x << endl;
- #define F first
- #define S second
- const int N = 2e5;
- vector<int> g[N + 1];
- int n;
- pair<pair<int, int>, pair<int, int>> dp[N + 1];
- int max_path[N + 1][2], parent[N + 1];
- // dp[i].first - (max1_len, max1_ver)
- // dp[i].second - (max2_len, max2_ver)
- void dfs(int cur, int prev) {
- parent[cur] = prev;
- vector<pair<int, int>> p = {{0, 0}, {0, 0}};
- for (auto v : g[cur]) {
- if (v == prev) continue;
- dfs(v, cur);
- p.pb(mp(1 + dp[v].F.F, v));
- }
- auto iter = max_element(all(p));
- dp[cur].F = {*iter};
- p.erase(iter);
- iter = max_element(all(p));
- dp[cur].S = {*iter};
- }
- void calc(int v) {
- if (max(max_path[v][0], max_path[v][1]) != 0) return;
- if (v == 1) {
- max_path[v][0] = dp[v].F.F;
- return;
- }
- if (max(max_path[parent[v]][1], max_path[parent[v]][0]) == 0) {
- calc(parent[v]);
- }
- max_path[v][0] = dp[v].F.F;
- max_path[v][1] = max_path[parent[v]][1] + 1;
- if (dp[parent[v]].F.S == v) {
- max_path[v][1] = max(max_path[v][1], 1 + dp[parent[v]].S.F);
- } else {
- max_path[v][1] = max(max_path[v][1], 1 + dp[parent[v]].F.F);
- }
- }
- signed main() // check the limits, dummy
- {
- ios::sync_with_stdio(false);
- cin >> n;
- for (int i = 0; i < n - 1; i++) {
- int u, v;
- cin >> u >> v;
- g[u].pb(v);
- g[v].pb(u);
- }
- /*
- firstly we gonna find max1_len and max2_len path
- for each node, where path includes only children nodes
- */
- dfs(1, -1);
- for (int i = 2; i <= n; i++) {
- calc(i);
- }
- for (int i = 1; i <= n; i++) {
- cout << max(max_path[i][0], max_path[i][1]) << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement