简单题选做 「[CSP2019]树的重心」

· · 题解

说一种比较无脑的主席树思路。

首先考虑部分分做法？40pts 就是暴力枚举切哪一条边。55pts 的链在瞎映射一通可以 O(1) 求出割完之后两棵树的重心分别是谁。75pts 的满二叉树大概是要先找出 \deg_x=2 的 x ，不难知道这个一定是根，找一波规律可以发现割掉每一条边之后，较小的那一半的重心必然是这个小连通块的根，较大的那部分的重心是对面的另一个儿子，也可能是原树的根。算一下就好了。

然后考虑满分怎么做。以下设 x 为当前点，y_k 为 x 的第 k 个孩子(顺序随便定的)，z 为 x 的重儿子，设 s 为割下来的连通块大小。

这个满分做法，我自己推的比较烦，不如其他人简洁。大概就是计算每个点当重心的次数。然后我分成了三部分算。对于一个点 x ，他可能成为重心，当且仅当：

Case 1 它子树内的某个子树被割了，它成为了重心

考虑此时这个小子树的子树大小需要满足什么条件。首先由于要分子树讨论，不妨设从 y_k 中割掉了一棵小子树。那么考虑要满足这么几个限制：

\begin{aligned} size_{y_k}-s&\leq \lfloor \frac{n-s}{2}\rfloor\\ n-size_x&\leq \lfloor \frac{n-s}{2}\rfloor\\ g_y&\leq \lfloor \frac{n-s}{2}\rfloor \end{aligned}

其中 g_y 为除去子树 y 后剩下的子树最大值。因为根据定义本质上并不关心那些较小的子树。

于是这部分就可以分子树查。发现本质上转化成了在 dfs 序上求「区间 [l,r] 内值域在 [a,b] 内的数有多少」，可以直接上主席树。然后这部分就做完了。

Case 2 它子树外的某个子树被割了，它成为了重心

此时还是不变，但是约束变为了

\begin{aligned} n-s-size_x&\leq \lfloor \frac{n-s}{2}\rfloor\\ z&\leq \lfloor \frac{n-s}{2}\rfloor\\ \end{aligned}

这部分也是可以直接主席树来求。但是注意解出来的 [l,r] 内可能会包含从 x 到根路径上点(祖先)的子树信息，可以对进退栈顺序开一棵线段树来容斥掉这一部分。

Case 3 它子树外某个不是子树的连通块被割了，它成为了重心

考虑此时割掉的一定是 x 到根路径上的一条边。发现本质上依旧是

\begin{aligned} n-s-size_x&\leq \lfloor \frac{n-s}{2}\rfloor\\ z&\leq \lfloor \frac{n-s}{2}\rfloor\\ \end{aligned}

于是还是维护一棵退栈顺序的线段树来维护这个。

然后以上的线段树可以换成树状数组。于是代码：

int _bit[N] ;

#define low(x) (x & -x)

il void mdf(int p, int x){
    for (  ; p <= n ; p += low(p)) _bit[p] += x ;
}
il int ask(int p){
    int ret = 0 ;
    for ( ; p ; p -= low(p)) ret += _bit[p] ;
    return ret ;
}
il int qry(int l, int r){ return ask(r) - ask(l - 1) ; }
void dfs5(int x, int fa){
    int l = max(1, n - 2 * sz[x]), s ;
    int r = n - 2 * sz[mson[x]], k, y, g ;
    if (r >= l){//Case 2
        res[x] += query(_rt[0], _rt[dfn[x] - 1], 1, n, l, r) ;
        res[x] += query(_rt[dfn[x] + sz[x] - 1], _rt[n], 1, n, l, r) ;
        res[x] -= qry(l, r) ;
    }
    pre[0] = 0 ; s = edg[x].size() ; suf[s] = 0 ;
    for (k = 0 ; k < s ; ++ k){
        y = edg[x][k] ;
        if (y == fa){ pre[k] = pre[max(0, k - 1)] ; continue ; }
        pre[k] = max(pre[max(k - 1, 0)], sz[y]) ;
    }
    for (k = s - 1 ; ~k ; -- k){
        y = edg[x][k] ;
        if (y == fa){ suf[k] = suf[k + 1] ; continue ; }
        suf[k] = max(suf[k + 1], sz[y]) ;
    }
    for (k = 0 ; k < s ; ++ k){ //Case 1
        y = edg[x][k] ;
        if (y == fa) continue ;
        g = max(n - sz[x], suf[k + 1]) ;
        if (k > 0) g = max(pre[k - 1], g) ;
        l = max(1, 2 * sz[y] - n), r = n - 2 * g ;
        if (r >= l)
            res[x] += query(_rt[dfn[y] - 1], _rt[dfn[y] + sz[y] - 1], 1, n, l, r) ;
    }
    mdf(sz[x], 1) ;
    for (auto k : edg[x])
        if (k != fa) dfs5(k, x) ;
    mdf(sz[x], -1) ;
}
void dfs6(int x, int fa, int qwq){//Case 3
    int t = sz[x] + qwq ;
    int r = n - 2 * sz[mson[x]] ;
    int l = max(1, n - 2 * sz[x]) ;
    if (r >= l)
        res[x] += qry(l, r) ;
    for (auto k : edg[x]){
        if (k == fa) continue ;
        mdf(t - sz[k], 1) ;
        dfs6(k, x, t - sz[k]) ;
        mdf(t - sz[k], -1) ;
    }
}
int main(){
//  freopen("centroid.in", "r", stdin) ;
//  freopen("centroid.out", "w", stdout) ;
    qr(T) ; int i, j, k ;
    while (T --){
        qr(n), ans = tot = 0 ;
        for (i = 1 ; i <= n ; ++ i)
            edg[i].clear(), mson[i] = res[i] = _bit[i] = 0 ;
        for (i = 1 ; i < n ; ++ i)
            qr(j), qr(k), edg[j].p_b(k), edg[k].p_b(j) ;
        dfs4(1, Id = 0) ; build(_rt[0], 1, n) ;
        for (i = 1 ; i <= n ; ++ i)
            upd(_rt[i], _rt[i - 1], 1, n, sz[rev[i]]) ;
        dfs5(1, 0) ; fill(_bit + 1, _bit + n + 1, 0) ; dfs6(1, 0, 0) ;
        for (int i = 1 ; i <= n ; ++ i) ans += 1ll * res[i] * i ; qw(ans, '\n') ;
    }
}

然后就做完了。复杂度是 O(n\log n)，但就是常数巨大…不知道为什么…感觉应该挺快才对啊（