Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- * Think twice, code once.
- * 1.integer overflow(maybe even long long overflow : (a+b >= c) -> (a >= c-b)
- * 2.runtime error
- * 3.boundary condition
- * ---------------------------------------------------------------------------------------
- * Author : zzy
- * Date : 2020-03-14-18.59.59 Saturday
- */
- #include <bits/stdc++.h>
- #define eb emplace_back
- #define mp make_pair
- #define mt make_tuple
- #define fi first
- #define se second
- #define pb push_back
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
- #define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
- #define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
- #define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
- #define rep(i, l, r) for (int i = (l); i <= (r); i++)
- #define per(i, r, l) for (int i = (r); i >= (l); i--)
- #define ms(x, y) memset(x, y, sizeof(x))
- #define SZ(x) ((int)(x).size())
- using namespace std;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- typedef vector<pii> vpi;
- typedef vector<vi> vvi;
- typedef long long i64;
- typedef vector<i64> vi64;
- typedef vector<vi64> vvi64;
- typedef pair<i64, i64> pi64;
- typedef double ld;
- template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
- template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
- const int maxn = 5*(int)1e5+100;
- int n, ans[maxn], no1[maxn], no2[maxn];
- vvi g(maxn);
- void dfs1(int u, int par) {
- for (int to : g[u]) {
- if(to == par) continue;
- dfs1(to, u);
- if (no1[to]+1 > no1[u]) {
- swap(no1[u], no2[u]);
- no1[u] = no1[to]+1;
- } else if (no1[to]+1 > no2[u]) {
- no2[u] = no1[to]+1;
- }
- }
- }
- void dfs2(int u, int par, int dist = 0) {
- ans[u] = max(no1[u], dist);
- for (int to : g[u]) {
- if (to == par) continue;
- if (no1[to]+1 == no1[u]) {
- if (no2[u]+1 > no1[to]) {
- swap(no1[to], no2[to]);
- no1[to] = no2[u]+1;
- }
- if (no2[u]+1 > no2[to]) {
- no2[to] = no2[u]+1;
- }
- dfs2(to, u, no2[u]+1);
- } else {
- if (no1[u]+1 > no1[to]) {
- swap(no1[to], no2[to]);
- no1[to] = no1[u]+1;
- }
- if (no1[u]+1 > no2[to]) {
- no2[to] = no1[u]+1;
- }
- dfs2(to, u, no1[u]+1);
- }
- }
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.precision(10);
- cout << fixed;
- #ifdef LOCAL_DEFINE
- freopen("input.txt", "r", stdin);
- #endif
- ms(no1, 0);
- ms(no2, 0);
- cin >> n;
- forn(i, n-1) {
- int u, v;
- cin >> u >> v;
- g[u].eb(v);
- g[v].eb(u);
- }
- dfs1(1, 0);
- // for1(i, n) {
- // cout << i << ' ' << no1[i] << ' ' << no2[i] << endl;
- // }
- dfs2(1, 0);
- // cerr << "YES" << endl;
- for1(i, n) cout << ans[i]+1 << '\n';
- #ifdef LOCAL_DEFINE
- cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement