Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #include <queue>
- #include <cstring>
- #define N 100005
- using namespace std;
- ifstream fin("smallworld.in");
- ofstream fout("smallworld.out");
- int n;
- int hmax[N];
- int dtop[N], T[N];
- vector <int> a[N];
- void citire() {
- fin >> n;
- for(int i = 1; i < n; ++i) {
- int p, q;
- fin >> p >> q;
- a[p].push_back(q);
- a[q].push_back(p);
- }
- }
- bool viz[N];
- void DFS(int x) {
- viz[x] = 1;
- bool check = 0;
- int m = 0;
- for(auto &i : a[x])
- if(!viz[i]){
- check = 1;
- DFS(i);
- T[i]=x;
- m = max(m, hmax[i]);
- }
- if(!check)
- hmax[x] = 0;
- else
- hmax[x] = m + 1;
- }
- void BFS(int x) {
- queue < int > q;
- q.push(x);
- dtop[x] = hmax[x];
- viz[x] = 1;
- while(!q.empty()) {
- int nod = q.front();
- q.pop();
- int frmax=0;
- for(auto &i:a[nod])
- if(!viz[i] && frmax<hmax[i])frmax=hmax[i];
- for(auto &i: a[nod]) {
- if(!viz[i]) {
- dtop[i]=max(dtop[T[i]]+1, frmax);
- viz[i]=1;
- q.push(i);
- }
- }
- }
- }
- int main()
- {
- citire();
- DFS(1);
- memset(viz, 0, n+1);
- BFS(1);
- for(int i=1;i<=n;i++)
- fout<<dtop[i]<<"\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement