Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- #define pb push_back
- #define endl "\n"
- using namespace std;
- const int N = 3e5 + 10;
- vector<int> gr[N];
- vector<int> vs, ans(N);
- int dist;
- pair<int, int> diam(int v, int pr = -1, int d = 0) {
- int bg = v;
- for(auto it: gr[v]) {
- if(it == pr) continue;
- pair<int, int> tmp = diam(it, v);
- if(tmp.first > d) {
- bg = tmp.second;
- d = tmp.first;
- }
- }
- return {d + 1, bg};
- }
- void add(int v, int pr = -1, int d = 0) {
- if(d == dist) ans[v] = 1;
- for(auto it: gr[v]) {
- if(it != pr) {
- add(it, v, d + 1);
- }
- }
- }
- main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin >> n;
- for(int i = 1; i < n; i++) {
- int l, r;
- cin >> l >> r;
- gr[l].pb(r);
- gr[r].pb(l);
- }
- pair<int,int> l = diam(1);
- pair<int,int> r = diam(l.second);
- dist = r.first - 1;
- add(l.second);
- add(r.second);
- for(int i = 1; i <= n; i++) {
- cout << dist + ans[i] << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement