CodeChef Diameter of Tree

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
int T, n, u, v, h[N], e[N], ne[N], idx;
int ans[N], down[N], f[N], up[N];
void add(int u, int v) {
    e[++idx] = v, ne[idx] = h[u], h[u] = idx;
}
void update(int x, int &a, int &b) {
    if (x > a) b = a, a = x;
    else if (x > b) b = x;
}
void push_up(int x, int &a, int &b, int &c) {
    if (x > a) c = b, b = a, a = x;
    else if (x > b) c = b, b = x;
    else if (x > c) c = x;
}
void dfs(int u) {
    int a = 0, b = 0; // 最远、次远距离
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        dfs(v);
        update(down[v] + 1, a, b); // 向下最远距离
        f[u] = max(f[u], f[v]);
    }
    down[u] = a;
    f[u] = max(f[u], a + b); // 子树直径
}
void dfs2(int u) {
    int lf = 0, rf = 0, ld = -1, md = -1, rd = -1, res = ans[u]; // 向上子树最长直径
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        ans[u] = max(ans[u], f[v]);
        update(f[v], lf, rf); // 子树最长、次长直径
        push_up(down[v], ld, md, rd); // 子节点向下最远距离
    }
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        up[v] = max(up[u] + 1, ld == down[v] ? md + 2 : ld + 2); // 向上最远距离
        ans[v] = max({res, lf == f[v] ? rf : lf, (ld == down[v] ? md : ld) + up[u] + 1});
        if (ld == down[v]) ans[v] = max(ans[v], md + rd + 2);
        else if (md == down[v]) ans[v] = max(ans[v], ld + rd + 2);
        else ans[v] = max(ans[v], ld + md + 2);
        dfs2(v);
    }
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int s = (n + 1) * 4;
        memset(h, 0, s);
        memset(f, 0, s);
        memset(down, 0, s);
        memset(up, 0, s);
        memset(ans, 0, s);
        idx = 0;
        for (int i = 1; i < n; ++i) {
            scanf("%d%d", &u, &v);
            add(u, v);
        }
        dfs(1);
        dfs2(1);
        for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}