万字长文·树上启发式合并入门经典

树上启发式合并是一种十分方便的将暴力算法优化至正解的优美的暴力

对于一类树上统计问题如果我们使用

可以解决一类树上统计问题

的点分治来做会不好写这样就可以引出树上启发式合并了

先给出例题

有一棵 n 个结点的以 1 号结点为根的有根树。
每个结点都有一个颜色，颜色是以编号表示的， i号结点的颜色编号为 $c_i$ 。
如果一种颜色在以 xx 为根的子树内出现次数最多，称其在以 xx 为根的子树中占主导地位。
显然，同一子树中可能有多种颜色占主导地位。
你的任务是对于每一个 i∈[1,n]，求出以 i 为根的子树中，占主导地位的颜色的编号和。

显然用点分治做不方便因为涉及到子树重心的子树与原树子树无关系

可以使用树上启发式合并

想到暴力直接开桶分别统计各子树

但是这样复杂度是是极高的对于一颗有着点分治重构树般优良平衡性的树可以达到接近$nlogn$的水平

不过若不平衡接近于$n^2$

可以发现对于一颗树某颗这棵树的子树的桶是可以重复利用的

选哪颗呢显然是最大的

我们求出所有重儿子先递归的对所有树的轻子树求答案然后清空桶

然后对重儿子求答案再对所有轻儿子求答案就得到了这棵树的所有子树的答案和这棵树的答案

看上去快不了多少但是因为若一颗小树与一颗大树合并这棵树最少扩大了一倍

所以每个节点最多可以被扩大遍历$logn$ 次总复杂度就达到了$nlogn$

我们就暴力完成了这道题qwq

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 100005
vector<int> mp[N];
int color[N],ap[N];
long long ans[N];
int n,m,son[N],siz[N],fa[N],dep[N],mx=0;
long long sum=0;
void dfs1(int x,int f,int deep)
{
  dep[x]=deep;fa[x]=f;siz[x]=1;siz[son[x]=0]=-1;
  for(int i=0;i<mp[x].size();i++)
  {
    int v=mp[x][i];
    if(v==f) continue;
    dfs1(v,x,deep+1);
    siz[x]+=siz[v];
    son[x]=siz[v]>siz[son[x]]?v:son[x];
  }
}
void dfs2(int x,int p)
{
  ap[color[x]]++;
  if(ap[color[x]]>mx)
  {
    mx=ap[color[x]];
    sum=color[x];
  }
  else if(mx==ap[color[x]])
    sum+=color[x];
  for(int i=0;i<mp[x].size();i++)
  {
    int v=mp[x][i];
    if(v==fa[x]||v==p) continue;
    dfs2(v,p);
  }
}
void dfs3(int x)
{
  for(int i=0;i<mp[x].size();i++)
  {
    int v=mp[x][i];
    if(v==fa[x]||v==son[x]) continue;
    dfs3(v);
    memset(ap,0,sizeof(ap));
    mx=0;
    sum=0;
  }
  if(son[x])
    dfs3(son[x]);
  dfs2(x,son[x]);
  ans[x]=sum;
}
int main()
{
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>color[i];
  for(int i=1,x,y;i<=n-1;i++)
  {
    cin>>x>>y;
    mp[x].push_back(y);
    mp[y].push_back(x);
  }
  dfs1(1,0,1);
  dfs3(1);
  for(int i=1;i<=n;i++)
    cout<<ans[i]<<" ";
  return 0;
}

← (untitled) 万字长文·动态树分治/动态动态规划/ddp入门经典 →