tumaryui

Untitled

Sep 4th, 2020
36
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define pb push_back
  4. #define endl "\n"
  5. using namespace std;
  6.  
  7. const int N = 3e5 + 10;
  8. vector<int> gr[N];
  9. vector<int> vs, ans(N);
  10. int dist;
  11. pair<int, int> diam(int v, int pr = -1, int d = 0) {
  12. int bg = v;
  13. for(auto it: gr[v]) {
  14. if(it == pr) continue;
  15. pair<int, int> tmp = diam(it, v);
  16. if(tmp.first > d) {
  17. bg = tmp.second;
  18. d = tmp.first;
  19. }
  20. }
  21. return {d + 1, bg};
  22. }
  23.  
  24. void add(int v, int pr = -1, int d = 0) {
  25. if(d == dist) ans[v] = 1;
  26.  
  27. for(auto it: gr[v]) {
  28. if(it != pr) {
  29. add(it, v, d + 1);
  30. }
  31. }
  32. }
  33. main() {
  34. ios_base::sync_with_stdio(0);
  35. cin.tie(0);
  36. cout.tie(0);
  37. int n;
  38. cin >> n;
  39. for(int i = 1; i < n; i++) {
  40. int l, r;
  41. cin >> l >> r;
  42. gr[l].pb(r);
  43. gr[r].pb(l);
  44. }
  45. pair<int,int> l = diam(1);
  46. pair<int,int> r = diam(l.second);
  47. dist = r.first - 1;
  48. add(l.second);
  49. add(r.second);
  50. for(int i = 1; i <= n; i++) {
  51. cout << dist + ans[i] << endl;
  52. }
  53. }
RAW Paste Data