Liveddd's Blog

愛にできることはまだあるかい

启发式合并

发表于 更新于 分类于
本文字数： 5.4k 阅读时长 ≈ 12 分钟

运用广泛的合并信息方式。

启发式算法是什么呢？
启发式算法是基于人类的经验和直观感觉，对一些算法的优化。

启发式合并又名 dsu on tree，常常运用在树上信息的合并，常见的并查集的按秩合并就是其中一种。并且常常与树链剖分相结合，从而达到较优的时间复杂度。

1.图论

1.1 重链剖分

1.1.1 CF275D Tree and Queries

考虑离线。我们对于一颗子树，先计算它的所有轻儿子的答案，但是删除轻儿子的信息。然后计算重儿子的答案并直接继承重儿子的信息。再暴力将所有轻儿子的信息合并上，最终计算该节点的答案。这样做是 $\mathcal O(n\log n)$。

看起来很不对？我们来分析一波。对于每一个点，到根节点，每有一条轻边就会使该点被暴力计算一次。根据树链剖分经典结论，每个点到根节点的轻边数不会超过 $\mathcal O( \log n)$ 条。那么每个点最多只会被暴力计算 $\mathcal O( \log n)$次，那么时间复杂度就是 $\mathcal O(n\log n)$ 。

当然也可以线段树合并。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e5+10;
template <class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m;
int c[N],q[N];
int tot,head[N],ver[N<<1],ne[N<<1];
int cnt,dfn[N],num[N],si[N],son[N];
int col[N],sum[N],ans[N];
vector<int>vec[N];
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
inline void insert(int x)
{
    sum[++col[c[x]]]++;
}
inline void del(int x)
{
    sum[col[c[x]]--]--;
}
void dfs1(int x,int fa)
{
    num[dfn[x]=++cnt]=x;
    si[x]=1;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs1(y,x);
        si[x]+=si[y];
        if(si[y]>si[son[x]])
            son[x]=y;
    }
}
void dfs2(int x,int fa,bool op)
{
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa||y==son[x])continue;
        dfs2(y,x,1);
    }
    if(son[x])
        dfs2(son[x],x,0);
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa||y==son[x])continue;
        for(int j=dfn[y];j<=dfn[y]+si[y]-1;j++)
            insert(num[j]);
    }
    insert(x);
    for(auto i:vec[x])
        ans[i]=sum[q[i]];
    if(op)
        for(int i=dfn[x];i<=dfn[x]+si[x]-1;i++)
            del(num[i]);
}
int main()
{
    read(n,m);
    for(int i=1;i<=n;i++)
        read(c[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u,v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=m;i++)
    {
        int u;
        read(u,q[i]);
        vec[u].push_back(i);
    }
    dfs1(1,0);
    dfs2(1,0,0);
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

通过上面的例子可以发现，启发式合并需要一个点的贡献很容易加上或者删除。

1.2 长链剖分

常常用来优化状态包含深度的 DP。

1.2.1 P3565 [POI2014]HOT-Hotels

设计 DP 状态，$f_{x,k}$ 表示子树 $x$ 中与 $x$ 距离为 $k$ 的点的个数。$g_{x,k}$ 表示 $dis(u,lca)=dis(v,lca)=dis(lca,x)+k$ 的 $(u,v)$ 个数。设 $y,y_1,y_2$ 均为 $x$ 的儿子节点，那么状态转移方程为：

通过前缀和容易做到 $\mathcal O(n^2)$。注意到状态与深度有关，于是我们可以用长链剖分优化 DP。对于当前点 $x$，我们直接继承它的长儿子的状态，再其余儿子合并计算。容易发现这样做显然只会计算长链上的每个节点一次，而长链总长度是 $\mathcal O(n)$ 的。所有总的复杂度就是 $\mathcal O(n)$。具体地可以通过指针实现对长儿子信息地直接继承。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<cstdio>
#define ll long long 
using namespace std;
const int N=1e5+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n;
int tot,head[N],ver[N<<1],ne[N<<1];
int dep[N],son[N];
int *f[N],*g[N],p[N<<2],*o=p;
ll ans;

inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
void dfs1(int x,int fa)
{
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs1(y,x);
        if(dep[son[x]]<dep[y])son[x]=y;
    }
    dep[x]=dep[son[x]]+1;
}
void dfs2(int x,int fa)
{
    if(son[x])f[son[x]]=f[x]+1,g[son[x]]=g[x]-1,dfs2(son[x],x);
    f[x][0]=1,ans+=g[x][0];
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa||y==son[x])continue;
        f[y]=o,o+=dep[y]<<1,g[y]=o,o+=dep[y]<<1;
        dfs2(y,x);
        for(int j=0;j<=dep[y];j++)
        {
            ans+=1ll*g[x][j+1]*f[y][j]+1ll*f[x][j]*g[y][j+1];
            g[x][j]+=g[y][j+1];
            if(j)g[x][j]+=f[x][j]*f[y][j-1],f[x][j]+=f[y][j-1];
        }
    }
}
int main()
{
    read(n);    
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u,v);
        add(u,v),add(v,u);
    }
    dep[1]=1;
    dfs1(1,0);
    f[1]=o,o+=dep[1]<<1,g[1]=o,o+=dep[1]<<1;
    dfs2(1,0);
    printf("%lld\n",ans);
    return 0;
}

2.

2.1 平衡树