526互联

MEX Tree

发布时间 2023-10-13 15:39:18作者: 2020fengziyang

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\)

\(sz_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]);
    }
}

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

两个端点都不为 \(0\)，两个端点分别为 \(x , y\)

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

    答案就是 \(0\)

  • \(i\) 是当前路径端点的子孙 \(lca (x , i) = x \or lca (y , i) = y\)

    答案就是对于端点子树大小 \(-\) \(sz_i\) 再乘上另一端子树大小

  • 否则，答案就是 \(sz_x * sz_y\)

有一个点为 \(0\) 的情况，另一个端点是 \(x\)

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

    答案就是 \(0\)

  • \(i\) 是当前路径端点的子孙

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

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

  • \(i\) 不属于上面的任意一种情况

    那么 \(i\) 就是当前路径的分叉，那么答案就是： \((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\) 加入当前路径中

1、两端都不为 \(0\)

  • \(i\) 已经在路径上了 \(lca (x , i) = i \or 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)\neq 0\) 插入失败

    2、\(x \neq 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;
}

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;
}