Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct Node{
- vector<int> links;
- int depth;
- };
- int n;
- vector<Node> tree;
- vector<bool> visited;
- int mxd;
- int mxn;
- vector<int> dist;
- void findDepth(int node){
- visited[node] = true;
- //cout << node << ", " << tree[node].depth << '\n';
- //cout << tree[node].depth << '\n';
- for(auto child: tree[node].links){
- if(!visited[child]){
- tree[child].depth = tree[node].depth+1;
- dist[child] = max(dist[child], tree[child].depth);
- if(tree[child].depth>mxd){
- mxd = tree[child].depth;
- mxn = child;
- }
- findDepth(child);
- }
- }
- }
- int main(){
- //freopen("treedistances.in", "r", stdin);
- cin >> n;
- tree.resize(n+1);
- visited.resize(n+1);
- dist.resize(n+1);
- int a, b;
- while(cin >> a){
- cin >> b;
- tree[a].links.push_back(b);
- tree[b].links.push_back(a);
- }
- findDepth(1);
- fill(visited.begin(), visited.end(), false);
- //cout << "==========" << '\n';
- mxd = 0;
- tree[mxn].depth = 0;
- findDepth(mxn);
- //cout << mxd << '\n';
- fill(visited.begin(), visited.end(), false);
- tree[mxn].depth = 0;
- findDepth(mxn);
- for(int i=1; i<=n; i++){
- cout << dist[i] << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
