产品摄影网站推荐,网站开发 自学,文创产品设计作品图片,网站续费方案CF1527D MEX Tree
MEX Tree - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 文章目录 CF1527D MEX Tree题目大意基本思路询问修改code 题目大意
给出一棵 n n n 个点的树#xff0c;点从 0 0 0 到 n − 1 n - 1 n−1 编号。定义一条路径的权值是路径上所有点编号的 m e …CF1527D MEX Tree
MEX Tree - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 文章目录 CF1527D MEX Tree题目大意基本思路询问修改code 题目大意
给出一棵 n n n 个点的树点从 0 0 0 到 n − 1 n - 1 n−1 编号。定义一条路径的权值是路径上所有点编号的 m e x mex mex 。对于每个 0 ≤ i ≤ n 0\le i\le n 0≤i≤n 求出 m e x mex mex 为 i i i 的路径有几条。注意这里统计的路径需要包括至少一条边。
一个集合的 m e x mex mex 定义为最小的不在集合中的非负整数。
基本思路
观察发现我们在处理 i i i 时 0 → i − 1 0\to i - 1 0→i−1 必须在一条路径上否则后面的答案就都是 0 0 0 s z i sz_i szi 表示以 i i i 为根的子树大小 s p sp sp 表示非 0 0 0 端点所在对于 0 0 0 的对应子树大小 下面会要用到倍增求 l c a lca lca
我们就可以搞一种类似于虚树操作的做法。
这里假设 0 0 0 是根
询问
所以询问可以分成 3 3 3 种情况 i i i 在当前的路径中 i i i 是当前路径端点的子孙 i i i 不属于上面的情况
然后 m e x 0 mex 0 mex0 和 m e x 1 mex 1 mex1 是特殊处理一下
当 m e x 0 mex 0 mex0 时
只要不经过 0 0 0 的路径都满足条件
所以答案就是 0 0 0 的所有子树里面任意选两个点的路径
当 m e x 1 mex 1 mex1 时
在 n n n 个点里面任意选两个点的方案数 − - − m e x 0 mex 0 mex0 的方案数
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]);}
}现在我们把其他询问分成两种情况
两个端点都不为 0 0 0两个端点分别为 x , y x , y x,y i i i 在路径上 $lca(x , i) i \or lca (y , i) i $ 答案就是 0 0 0 i i i 是当前路径端点的子孙 KaTeX parse error: Undefined control sequence: \or at position 17: …ca (x , i) x \̲o̲r̲ ̲lca (y , i) y 答案就是对于端点子树大小 − - − s z i sz_i szi 再乘上另一端子树大小 否则答案就是 s z x ∗ s z y sz_x * sz_y szx∗szy
有一个点为 0 0 0 的情况另一个端点是 x x x i i i 在当前路径中 l c a ( x , i ) i lca (x , i) i lca(x,i)i 答案就是 0 0 0 i i i 是当前路径端点的子孙 i i i 是不为零的那个端点的子孙 l c a ( x , i ) x lca (x , i) x lca(x,i)x那么答案就是 ( s i z [ x ] − s i z [ i ] ) ∗ ( s i z [ 0 ] − s p ) (siz[x] - siz[i]) * (siz[0] - sp) (siz[x]−siz[i])∗(siz[0]−sp) i i i 是 0 0 0 的子孙 l c a ( x , i ) 0 lca (x , i) 0 lca(x,i)0 那么答案就是 ( s i z [ 0 ] − s p − s i z [ i ] ) ∗ s i z [ x ] (siz[0] - sp - siz[i]) * siz[x] (siz[0]−sp−siz[i])∗siz[x] i i i 不属于上面的任意一种情况 那么 i i i 就是当前路径的分叉那么答案就是 ( s i z [ 0 ] − s p ) ∗ s i z [ x ] (siz[0] - sp) * siz[x] (siz[0]−sp)∗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;
}修改
尝试将 i i i 加入当前路径中
1、两端都不为 0 0 0 i i i 已经在路径上了 KaTeX parse error: Undefined control sequence: \or at position 17: …ca (x , i) i \̲o̲r̲ ̲lca (y , i) i 就不用管了 i i i 是其中一端的子孙 $lca(x , i) x \or lca (y , i) y $ 直接把那个端点设为 i i i 就好了 如果不属于上面的两种情况 那么就是分叉直接下面的答案都为 0 0 0 就好了
2、至少有一端是 0 0 0 的情况 如果两端都是 0 0 0 直接把一端设为 i i i i i i 已经在路径上了 l c a ( x , i ) i lca (x , i) i lca(x,i)i 不用管了 l c a ( x , i ) x lca (x , i) x lca(x,i)x x i x i xi 不属于上面的情况 1、分叉 l c a ( x , i ) ≠ 0 lca (x , i)\neq 0 lca(x,i)0 插入失败 2、 x ≠ 0 x \neq 0 x0 且 l c a ( x , i ) 0 lca (x , i) 0 lca(x,i)0 那么 y i y i yi
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;
}code
#include bits/stdc.h
#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;
}
