【题解】P8968 路径压缩 思维 数据结构

· · 题解

因为这里是 1C 的题解不是 2C 的题解，所以就不在叙述博弈的策略与方法了，继续摆出 1C 的结论： 一直向树的上方跳，令目前的答案为 x，另一棵子树的大小是 a， 则 x\gets x+\min\{x,a\}。

考虑使用数据结构优化这个过程。

O(n\log n\log |V|)

将 \min 分开， x \gets 2x (x < a) \ , \ x\gets x+a(x\geq a)，发现前面那种情况 x 会倍增，所以最多发生 \log V 次，需要特殊处理，其它都是直接加上。

dfs 整棵树的时候用数据结构维护这个操作序列：

$$ (x+\sum_{j=i+1}^{p-1} a_j) < a_p$$ 即 $$a_p-\sum_{j=1}^{p-1} a_j> x-\sum_{j=1}^i a_j$$ 使用线段树维护左边的值，需要支持区间加，二分。 可以在线段树上二分单次 $O(\log n)$ 解决，总复杂度是 $O(n\log n\log |V|)$，可以过 $10^5$。 线段树可以维护 “区间加，区间最值”，也可以维护“单点修改，前缀和最值” 。 基于后一种可并的信息 ， 可以用倍增维护向上 $2^k$ 跳层中不会触发翻倍的最大值，可以做到小常数的 $O(n\log n\log |V|)$，场上很多人都卡过去了 $10^6$。 --- ### $O(n\log |V|)

跳 \log 次的复杂度是扔不掉了，考虑优化跳的过程：

倍增时很多路径段本身是整体的 ，但是被拆成了很多个路径段，每个路径都被拆成了 \log 个，是不优秀的，考虑把这个跳的整段性展现出来，用一种类似并查集路径压缩的思想 ：

最初每个点的父亲是自己，如果它一定不会触发父亲的翻倍就把它和父亲压缩到一起，这样每一步都会跳到某段较长的一定不会触发翻倍的段的顶端。

具体实现：

对于每个点维护这个不触发倍增较长段的阈值 l，顶端 t，跳到顶端后需要加的值 a，加入一个新的点后，如果 l+a\geq l_t，也就是说不触发这个段一定就不会触发上面的段，所以直接连向它上面段的断顶，继续直到段顶满足 l+a < l_t。

每经过一个这样的段， l 的值至少翻倍（l+a\geq2l），所以最多经过 \log |V| 个这样的段，直接跳就行了，复杂度 O(n\log |V|)。

部分代码：


struct element {
    int limit , addtion , target ;
};  
vector< element >  Q ; 
void dfs(int x) {
    if(!x) return ; 
    int p = (int) Q.size( ) - 1 ;
    ans[x] = siz[x] ; 
    int cnt = 0 ; 
    while(p > 0) {
        auto [limit,addtion,target] = Q[p] ; 
            ++cnt ; 
        if(ans[x] >= limit) {
            ans[x] += addtion ;
            p = target ;
            continue; 
        }
        ans[x] <<= 1; 
        p -- ; 
    }
    if(son[x][0])    
    {
        if(son[x][1]) {
        auto nw = (element) {siz[son[x][1]],siz[son[x][1]],(int) Q.size( ) - 1} ;
        while(nw.limit+nw.addtion >= Q[nw.target].limit) nw.addtion += Q[nw.target].addtion , nw.target = Q[nw.target].target ;
        Q.push_back(nw);    
        }
        dfs(son[x][0]) ; 
        if(son[x][1]) Q.pop_back ( ) ;
    }
    if(son[x][1]) {
        if(son[x][0]) {
        auto nw = (element) {siz[son[x][0]],siz[son[x][0]],(int) Q.size( ) - 1} ;
        while(nw.limit+nw.addtion >= Q[nw.target].limit) nw.addtion += Q[nw.target].addtion , nw.target = Q[nw.target].target ;
        Q.push_back(nw);
        }
        dfs(son[x][1]) ; 
        if(son[x][0]) Q.pop_back ( ) ; 
    }    
}

于 1 月 25 日排在最优解第二。

完整代码

收录于《超级无敌神仙炫酷无敌原神大王好题》 。