Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

CF1009F Dominant Indices

发表于 分类于
本文字数： 4.1k 阅读时长 ≈ 4 分钟
标签：        

LuoGu: CF1009F Dominant Indices

CF: F. Dominant Indices

使用树上启发式合并，$O(n \log n)$ 卡过。

维护一个 $cnt$ 表示每个深度有多少个数。对于相同的答案，注意取最小的 $k$ 。

查看代码 
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
69
70
71
72
73
74
75
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10, M = N << 1;
int n, d[N], p[N], sz[N], son[N];
int mn, mx, cnt[N], ans[N];
int idx, hd[N], nxt[M], edg[M];
void dfs1(int x)
{
    sz[x] = 1;
    son[x] = -1;
    for (int i = hd[x]; ~i; i = nxt[i])
        if (!d[edg[i]])
        {
            p[edg[i]] = x;
            d[edg[i]] = d[x] + 1;
            dfs1(edg[i]);
            sz[x] += sz[edg[i]];
            if (son[x] == -1 || sz[edg[i]] > sz[son[x]])
                son[x] = edg[i];
        }
}
void update(int x, int op, int avoid)
{
    cnt[d[x]] += op;
    if (cnt[d[x]] > mx)
    {
        mn = d[x];
        mx = cnt[d[x]];
    }
    else if (cnt[d[x]] == mx)
        mn = min(mn, d[x]);
    for (int i = hd[x]; ~i; i = nxt[i])
        if (edg[i] != p[x] && edg[i] != avoid)
            update(edg[i], op, avoid);
}
void dfs2(int x, int op)
{
    for (int i = hd[x]; ~i; i = nxt[i])
        if (edg[i] != son[x] && edg[i] != p[x])
            dfs2(edg[i], 0);
    if (~son[x])
        dfs2(son[x], 1);
    update(x, 1, son[x]);
    ans[x] = mn - d[x];
    if (!op)
    {
        update(x, -1, 0);
        mx = mn = 0;
    }
}
void add(int a, int b)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        hd[i] = -1;
    for (int i = 1, u, v; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    d[1] = 1;
    dfs1(1);
    dfs2(1, 0);
    for (int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
    return 0;
}

正解是长链剖分，复杂度为 $O(n)$​ 。

查看代码 
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
69
70
71
72
73
74
#include <cstdio>
#include <vector>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e6 + 10;
int n, d[N], son[N], v[N], ans[N];
int *f[N], *cur = v;
vector <int> g[N];
void dfs1 (int x, int fa)
{
    for (int i : g[x])
        if (i ^ fa)
        {
            dfs1(i, x);
            (d[i] > d[son[x]]) && (son[x] = i);
        }
    d[x] = d[son[x]] + 1;
}
void dfs2 (int x, int fa)
{
    f[x][0] = 1;
    if (son[x])
    {
        f[son[x]] = f[x] + 1;
        dfs2(son[x], x);
        ans[x] = ans[son[x]] + 1;
    }
    for (int i : g[x])
        if (i ^ fa && i ^ son[x])
        {
            f[i] = cur, cur += d[i];
            dfs2(i, x);
            for (int k = 1; k <= d[i]; k++)
            {
                f[x][k] += f[i][k - 1];
                (f[x][k] > f[x][ans[x]] || (f[x][k] == f[x][ans[x]] && k < ans[x])) && (ans[x] = k);
            }
        }
    f[x][ans[x]] == 1 && (ans[x] = 0);
}
int main ()
{
    read(n);
    for (int i = 1, a, b; i < n; i++)
    {
        read(a), read(b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs1(1, 0);
    f[1] = cur, cur += d[1];
    dfs2(1, 0);
    for (int i = 1; i <= n; i++)
        write(ans[i]), puts("");
    return 0;
}
相关文章