题解 CF600E 【Lomsat gelral】

辰星凌 · 2020-02-20 11:07:19 · 题解

【题解】Lomsat gelral [CF600E]

\mathcal{My}\ \mathcal{Blog}

【前言】

树上启发式合并 \text{Dsu on tree} 一般用来解决一类不带修的子树查询问题（据说这玩意儿原名 静态链分治？）。

其核心思想为：利用重链剖分的性质优化子树贡献的计算。

由于 \text{zwfymqz} 巨佬一讲得比较简略，一开始我并没有理解到其精髓，导致一度怀疑其时间复杂度的合理性，甚至连代码都看不懂。
后来看了看 \text{YudeS} 楪 神仙的另一种写法 自己手玩了几棵树就懂了。
个人认为后者更好理解，因此本文讲解后者，可能与网上大多数写法略有不同。

【算法实现】

先看板题：\text{Lomsat gelral [CF600E]}

题目描述：给出一棵 n 个结点的树，每个结点都有一种颜色编号，求该树中每棵子树里的出现次数最多的颜色的编号和。

算法流程如下：

• 跑一遍 dfs 预处理出每个点的重儿子 son 。

• 对于一个点 x，首先遍历计算他所有轻儿子的 ans，并且每算完一个儿子就要清除它的所有贡献。
  接下来计算重儿子 son[x] 的答案，并保留 subtree(son[x]) 中所有点的贡献，然后再暴力加入 subtree(x) 中除 subtree(son[x]) 以外的所有点的贡献，此时即可得到 ans[x] 。
  随后回溯到 fa[x]，如果 x 是 fa[x] 的轻儿子，那么将在 x 这一波计算下来的贡献全部清除，反之则全部保留。

【时间复杂度】

经过多次不靠谱的手玩尝试，我们可以发现：每一个点只会在其到根路径中若干重链交界处被统计（也即是从该点到根路径上的轻边数量）。

而由于重链剖分的性质，任意一个点往上跳时所经过的重链数量不超过 O(logn)，所以重链交界处（轻边）的数量也不会超过 O(logn)，因此每个点的统计次数也为 O(logn) 。

总复杂度为：O(nlogn)，并带上一个通常为 O(1) 的常数（统计一个点贡献的复杂度）。

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int o,n,m,x,y,t,K,tmp,A[N],Q[N],cnt[N],son[N],size[N],head[N];LL ans,Ans[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs(Re x,Re fa){//预处理重儿子
    size[x]=1;
    for(Re i=head[x],to;i;i=a[i].next)
        if((to=a[i].to)!=fa){
            dfs(to,x),size[x]+=size[to];
            if(size[to]>size[son[x]])son[x]=to;
        }
}
inline void CL(){//清空贡献，从zero开始
    while(t)cnt[Q[t--]]=0;ans=tmp=0;
}
inline void insert(Re x){//加入点x的贡献
    ++cnt[Q[++t]=A[x]];
    if(cnt[A[x]]>tmp)tmp=cnt[ans=A[x]];
    else if(cnt[A[x]]==tmp)ans+=A[x];
}
inline void addson(Re x,Re fa){//加入subtree(x)的贡献（以x为根的整棵子树）
    insert(x);
    for(Re i=head[x],to;i;i=a[i].next)
        if((to=a[i].to)!=fa)addson(to,x);
}
inline void sakura(Re x,Re fa){
    for(Re i=head[x],to;i;i=a[i].next)
        if((to=a[i].to)!=fa&&to!=son[x])sakura(to,x),CL();//计算轻儿子的答案并清空贡献
    if(son[x])sakura(son[x],x);//计算重儿子的答案并保留subtree(son[x])（以son[x]为根的整棵子树贡献）
    for(Re i=head[x],to;i;i=a[i].next)
        if((to=a[i].to)!=fa&&to!=son[x])addson(to,x);//加入subtree(x)-subtree(son[x])-x（以x的所有轻儿子为根的子树贡献）
    insert(x),Ans[x]=ans;//注意还要把x的贡献也加进去
}
int main(){
//  freopen("123.txt","r",stdin);
    in(n),m=n-1;
    for(Re i=1;i<=n;++i)in(A[i]);
    while(m--)in(x),in(y),add(x,y),add(y,x);
    dfs(1,0),sakura(1,0);
    for(Re i=1;i<=n;++i)printf("%lld ",Ans[i]);
}

【参考资料】

• \text{Dsu on tree} 入门

【后记】

\mathcal{My}\ \mathcal{Blog}

再补充一下另一种做法吧。

大致浏览了网上的题解，常见做法有以下几种：

• 线段树合并（空间巨大）

但就是没找到一篇 \text{DFS} 序 + 分治，让我来做全网第一篇吧（只是我没有找到，希望不要打脸吧）。

【分析】

子树查询转到序列上后其本质是一系列的区间查询，我们知道，要想用分治是需要满足一定单调性的，那么这些区间是否有我们想要的性质呢？

先给出一些定义：

【引理】

抛结论：
设 i'<i，若存在一个 j 满足 i \leqslant j \leqslant Rdfn(i) 且 i' \leqslant j \leqslant Rdfn(i')，那么 一定有 Rdfn(i') \geqslant Rdfn(i) 。
（按照 \text{YudeS} 楪 巨佬所说，穿过 j 的区间有互相包含的关系，放在此处即是区间 [i,Rdfn(i)] 被包含于 [i',Rdfn(i')] 中 ）。

其实很简单，稍想一下就明白了。

证明：
由给出的两个条件可知 idx(j) \in subtree(idx(i)) 且 idx(j) \in subtree(idx(i'))，所以 idx(i),idx(i') 均为idx(j) 的祖先节点。
又因为 i'<i，且任意一个节点 x 的所有祖先都在从根到 x 的简单路径上，所以 idx(i') 应为 idx(i) 的祖先节点，于是有 Rdfn(i') \geqslant Rdfn(i)。

【算法实现】

回到这道题，有了上面那个性质，用分治已经很显然了吧，对于一层 (L,mid,R) 扫一遍计算出：满足 L \leqslant i \leqslant mid 且 mid+1 \leqslant Rdfn(i) \leqslant R 的所有 ans[i] 。

时间复杂度为：O(nlogn)。

核心操作就一个分治函数，好想又好写，居然没人用....

像这种 dot 的题应该都可以用 \text{DFS} 序 + 回滚莫队/分治 搞吧，insert 函数都不需要改，时间复杂度和分治基本一样（蒟蒻瞎口胡，可信度极低）

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int o,n,m,x,y,t,tmp,dfn_O,A[N],Q[N],cnt[N],dfn[N],idx[N],size[N],head[N];LL ans,Ans[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs(Re x,Re fa){//预处理dfn序
    idx[dfn[x]=++dfn_O]=x,size[x]=1;
    for(Re i=head[x],to;i;i=a[i].next)
        if((to=a[i].to)!=fa)dfs(to,x),size[x]+=size[to];
}
inline void CL(){//清空贡献，从zero开始
    while(t)cnt[Q[t--]]=0;ans=tmp=0;
}
inline void insert(Re x){//加入点x的贡献
    ++cnt[Q[++t]=A[x]];
    if(cnt[A[x]]>tmp)tmp=cnt[ans=A[x]];
    else if(cnt[A[x]]==tmp)ans+=A[x];
}
inline void sakura(Re L,Re R){//分治解决(L,R)
    if(L==R){if(size[L]==1)Ans[L]=A[L];return;}
    Re mid=L+R>>1;
    sakura(L,mid),sakura(mid+1,R);//递归解决下面的
    Re p=mid;CL();//搞一个指针p
    for(Re i=mid,j;i>=L&&(j=i+size[idx[i]]-1)<=R;--i){//当j=Rdfn(i)大于R时就可以结束了
        insert(idx[i]);
        if(j<=mid)continue;//只解决对于j>mid的部分
        while(p<j)insert(idx[++p]);//由性质可知满足大于mid的那部分j是单调递增的，不断移动指针p即可
        Ans[idx[i]]=ans;//获得答案
    }
}
int main(){
//  freopen("123.txt","r",stdin);
    in(n),m=n-1;
    for(Re i=1;i<=n;++i)in(A[i]);
    while(m--)in(x),in(y),add(x,y),add(y,x);
    dfs(1,0),sakura(1,n);
    for(Re i=1;i<=n;++i)printf("%lld ",Ans[i]);
}

【参考资料】

• \text{YudeS} 楪 神仙的 \text{DFS} 序分治代码。