CF1527D MEX Tree

CF1527D MEX Tree

MEX Tree - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目大意

给出一棵 $n$ 个点的树，点从 $0$ 到 $n-1$ 编号。定义一条路径的权值是路径上所有点编号的 $mex$ 。对于每个 $0\le i\le n$ 求出 $mex$ 为 $i$ 的路径有几条。注意，这里统计的路径需要包括至少一条边。

一个集合的 $mex$ 定义为最小的不在集合中的非负整数。

基本思路

观察发现，我们在处理 $i$ 时，$0\to i-1$ 必须在一条路径上，否则后面的答案就都是 $0$

$s{z}_i$ 表示以 $i$ 为根的子树大小

$sp$ 表示非 $0$ 端点所在对于 $0$ 的对应子树大小

下面会要用到倍增求 $lca$

我们就可以搞一种类似于虚树操作的做法。

这里假设 $0$ 是根

询问

所以询问可以分成 $3$ 种情况：

• $i$ 在当前的路径中
• $i$ 是当前路径端点的子孙
• $i$ 不属于上面的情况

然后 $mex=0$ 和 $mex=1$ 是特殊处理一下

当 $mex=0$ 时：

只要不经过 $0$ 的路径都满足条件

所以答案就是 $0$ 的所有子树里面任意选两个点的路径

当 $mex=1$ 时：

在 $n$ 个点里面任意选两个点的方案数 $-$ $mex=0$ 的方案数

LL gs (LL x) { return x * (x - 1) / 2; }
void pre_ans () {
    ans[1] = gs (sz[0] - sz[1]);
    int y;
    for (int i = hd[0] ; i ; i = e[i].nt) {
        y = e[i].to;
        ans[0] += gs (sz[y]);
        int lca = Lca (y , 1);
        if (lca == y) ans[1] -= gs (sz[y] - sz[1]);
        else ans[1] -= gs (sz[y]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

现在我们把其他询问分成两种情况

两个端点都不为 $0$，两个端点分别为 $x,y$

• $i$ 在路径上 $lca(x , i) =i \or lca (y , i) = i $

  答案就是 $0$

• $i$ 是当前路径端点的子孙 KaTeX parse error: Undefined control sequence: \or at position 17: …ca (x , i) = x \̲o̲r̲ ̲lca (y , i) = y

  答案就是对于端点子树大小 $-$ $s{z}_i$ 再乘上另一端子树大小

• 否则，答案就是 $s{z}_x\ast s{z}_y$

有一个点为 $0$ 的情况，另一个端点是 $x$

• $i$ 在当前路径中 $lca(x,i)=i$

  答案就是 $0$

• $i$ 是当前路径端点的子孙

  $i$ 是不为零的那个端点的子孙$lca(x,i)=x$，那么答案就是： $(siz[x]-siz[i])\ast (siz[0]-sp)$

  $i$ 是 $0$ 的子孙 $lca(x,i)=0$ ，那么答案就是： $(siz[0]-sp-siz[i])\ast siz[x]$

• $i$ 不属于上面的任意一种情况

  那么 $i$ 就是当前路径的分叉，那么答案就是： $(siz[0]-sp)\ast siz[x]$

LL gt_ans (int x) {
    int lca1 = Lca (x , l) , lca2 = Lca (x , r);
    LL ans1 , ans2;
    if (r) {
        ans1 = sz[l] , ans2 = sz[r];
        if (lca1 == x || lca2 == x) return 0;
        else if (lca1 == l) ans1 -= sz[x];
        else if (lca2 == r) ans2 -= sz[x];
    }
    else {
        ans1 = sz[l] , ans2 = sz[r] - sp;
        if (lca1 == x || lca2 == x) return 0;
        else if (lca1 == l) ans1 -= sz[x];
        else if (lca1 == 0) ans2 -= sz[x];
    }
    return ans1 * ans2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

修改

尝试将 $i$ 加入当前路径中

1、两端都不为 $0$

• $i$ 已经在路径上了 KaTeX parse error: Undefined control sequence: \or at position 17: …ca (x , i) = i \̲o̲r̲ ̲lca (y , i) = i

  就不用管了

• $i$ 是其中一端的子孙 $lca(x , i) = x \or lca (y , i) = y $

  直接把那个端点设为 $i$ 就好了

• 如果不属于上面的两种情况

  那么就是分叉，直接下面的答案都为 $0$ 就好了

2、至少有一端是 $0$ 的情况

• 如果两端都是 $0$

  直接把一端设为 $i$

• $i$ 已经在路径上了 $lca(x,i)=i$

  不用管了

• $lca(x,i)=x$

  $x=i$

• 不属于上面的情况

  1、分叉 $lca(x,i)\ne 0$ 插入失败

  2、$x\ne 0$ 且 $lca(x,i)=0$ ，那么 $y=i$

bool add (int x) {
    int lca1 = Lca (l , x) , lca2 = Lca (r , x);
    if (r) {
        if (lca1 == l) {
            l = x;
            return 1;
        }
        else if (lca1 == x) return 1;
        if (lca2 == r) {
            r = x;
            return 1;
        }
        else if (lca2 == x) return 1;
    }
    else {
        if (lca1 && (lca1 != l && lca1 != x)) return 0;
        else if (lca1 == l ) {
            l = x;
            return 1;
        }
        else if (lca1 == x) return 1;
        else if (lca1) return 0;
        else {
            r = x;
            return 1;
        }
    }
    return 0;
}
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

code

#include 
#define fu(x , y , z) for(int x = y ; x <= z ; x ++) 
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
#define LL long long
using namespace std;
const int N = 6e5 + 5 , inf = 2e5;
int n , sz[N] , hd[N] , cnt , fa[N] , sp , dep[N] , f[N << 1][30] , l , r;
LL tw[30] , ans[N] , lg2[inf + 5];
struct E {
    int to , nt;
} e[N << 1];
void add (int x , int y) { e[++cnt].to = y , e[cnt].nt = hd[x] , hd[x] = cnt; }
int Lca (int x , int y) {
    int flg;
    while (dep[x] != dep[y]) {
        flg = 0;
        if (dep[x] > dep[y]) swap (x , y);
        fd (i , 25 , 0) {
            while (dep[f[y][i]] > dep[x]) {
                y = f[y][i];
                flg = 1;
            }
        }
        if (!flg) break;
    }
    while (dep[x] != dep[y]) {
        if (dep[x] > dep[y]) swap (x , y);
        y = f[y][0];
    }
    while (x != y) {
        flg = 0;
        fd (i , 25 , 0) {
            while (f[x][i] != f[y][i]) {
                x = f[x][i] , y = f[y][i];
                flg = 1;
            }
        }
        if (!flg) break;
    }
    while (x != y)
        x = f[x][0] , y = f[y][0];
    return x;
}
void dfs1 (int x) {
    int y;
    sz[x] = 1;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        if (fa[x] == y) continue;
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs1 (y);
        sz[x] += sz[y];
    }
}
void gt_f () {
    fu (i , 0 , n - 1) 
        fu (j , 1 , 25) 
            f[i][j] = 0;
    dep[0] = 1;
    dfs1 (0);
    fu (i , 0 , n - 1) 
        f[i][0] = fa[i];
    fu (j , 1 , 25) {
        fu (i , 0 , n - 1) {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
}
LL gs (LL x) { return x * (x - 1) / 2; }
void pre_ans () {
    ans[1] = gs (sz[0] - sz[1]);
    int y;
    for (int i = hd[0] ; i ; i = e[i].nt) {
        y = e[i].to;
        ans[0] += gs (sz[y]);
        int lca = Lca (y , 1);
        if (lca == y) ans[1] -= gs (sz[y] - sz[1]);
        else ans[1] -= gs (sz[y]);
    }
}
bool add (int x) {
    int lca1 = Lca (l , x) , lca2 = Lca (r , x);
    if (r) {
        if (lca1 == l) {
            l = x;
            return 1;
        }
        else if (lca1 == x) return 1;
        if (lca2 == r) {
            r = x;
            return 1;
        }
        else if (lca2 == x) return 1;
    }
    else {
        if (lca1 && (lca1 != l && lca1 != x)) return 0;
        else if (lca1 == l ) {
            l = x;
            return 1;
        }
        else if (lca1 == x) return 1;
        else if (lca1) return 0;
        else {
            r = x;
            return 1;
        }
    }
    return 0;
}
LL gt_ans (int x) {
    int lca1 = Lca (x , l) , lca2 = Lca (x , r);
    LL ans1 , ans2;
    if (r) {
        ans1 = sz[l] , ans2 = sz[r];
        if (lca1 == x || lca2 == x) return 0;
        else if (lca1 == l) ans1 -= sz[x];
        else if (lca2 == r) ans2 -= sz[x];
    }
    else {
        ans1 = sz[l] , ans2 = sz[r] - sp;
        if (lca1 == x || lca2 == x) return 0;
        else if (lca1 == l) ans1 -= sz[x];
        else if (lca1 == 0) ans2 -= sz[x];
    }
    return ans1 * ans2;
}
int main () {
    tw[0] = 1ll;
    fu (i , 1 , 25) tw[i] = 1ll * tw[i - 1] * 2;
    int T , u , v;
    scanf ("%d" , &T);
    while (T --) {
        scanf ("%d" , &n);
        cnt = 0;
        fu (i , 0 , n) ans[i] = hd[i] = fa[i] = 0;
        fu (i , 0 , n) 
            fu (j , 0 , 25) 
                f[i][j] = -1;
        fu (i , 1 , n - 1) {
            scanf ("%d%d" , &u , &v);
            add (u , v) , add (v , u);
        }
        gt_f ();
        pre_ans ();
        for (int i = hd[0] ; i ; i = e[i].nt) {
            if (Lca (e[i].to , 1) == e[i].to) {
                sp = sz[e[i].to];
                break;
            }
        }
        l = r = 0;
        fu (i , 2 , n) {
            if (!add (i - 1)) break;
            if (i == n) {
                ans[i] = 1;
                break;
            }
            ans[i] = gt_ans (i);
        }
        fu (i , 0 , n)
            printf ("%lld " , ans[i]);
        printf ("\n");
    }
    return 0;
}
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166