Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * @Author: dnhirapara
- * @Problem: B_Dynamic_Diameter
- * @Time: 28-August-2020 : ( 16:10:06 )
- */
- #include <bits/stdc++.h>
- using namespace std;
- /************defination************/
- #define endl "\n"
- #define logger(x) cout << __LINE__ << ": " << #x << " -> " << (x) << endl;
- #define ll long long int
- #define ull unsigned long long int
- const int size = 3e5 + 5;
- vector<int> g[size];
- vector<bool> vis(size);
- vector<int> deg(size);
- int maxDist;
- int maxNode;
- vector<int> update;
- vector<int> update1;
- bool secDfs = false;
- void dfs(int node, int lvl)
- {
- vis[node] = true;
- for (auto i : g[node])
- {
- if (vis[i] == false)
- {
- dfs(i, lvl + 1);
- }
- }
- if (secDfs && maxDist == lvl)
- {
- update.push_back(node);
- }
- if (maxDist < lvl)
- {
- if (secDfs)
- {
- update.clear();
- update.push_back(node);
- }
- maxDist = lvl;
- maxNode = node;
- }
- }
- int getDia(int n)
- {
- //first run
- secDfs = false;
- maxDist = -1;
- for (int i = 0; i < n + 1; i++)
- {
- vis[i] = false;
- }
- dfs(1, 0);
- maxDist = -1;
- int temp = maxNode;
- secDfs = true;
- for (int i = 0; i < n + 1; i++)
- {
- vis[i] = false;
- }
- dfs(maxNode, 0);
- update.push_back(temp);
- update1 = update;
- // second run
- update.clear();
- secDfs = false;
- maxDist = -1;
- for (int i = 0; i < n + 1; i++)
- {
- vis[i] = false;
- }
- dfs(maxNode, 0);
- maxDist = -1;
- temp = maxNode;
- secDfs = true;
- for (int i = 0; i < n + 1; i++)
- {
- vis[i] = false;
- }
- dfs(maxNode, 0);
- update.push_back(temp);
- if (update1.size() < update.size())
- {
- update1 = update;
- }
- //vis false
- for (int i = 0; i < n + 1; i++)
- {
- vis[i] = false;
- }
- return maxDist;
- }
- //@time comp :
- //@space comp :
- int main()
- {
- // ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- // cin.ignore(); must be there when using getline(cin, s)
- ll tc = 1;
- //cin >> tc;
- while (tc--)
- {
- int n;
- cin >> n;
- int u, v;
- for (int i = 0; i < n - 1; i++)
- {
- cin >> u >> v;
- g[u].push_back(v);
- g[v].push_back(u);
- }
- int degR = getDia(n);
- for (auto i : update1)
- {
- vis[i] = true;
- }
- for (int i = 1; i <= n; i++)
- {
- if (vis[i])
- {
- cout << degR + 1 << endl;
- }
- else
- {
- cout << degR << endl;
- }
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment