树上启发式合并

树上启发式合并

注意事项：多测时，需要清空dfn和big，同时要将对根的 dfs1 的 keep 标记置为 0。

树上启发式合并一般解决的是不带修改对子树内的询问，可以通过对所有儿子暴力求答案，但删除轻儿子的结果，保留重儿子的结果，从而保证了复杂度。

树上启发式合并的流程为：

  1. 遍历轻子树，递归求解答案，不保留它们的影响。
  2. 遍历重子树，递归求解答案，保留它们的影响。
  3. 再遍历轻子树，保留它们的影响。

由于一个结点到根结点最多经过 O(log⁡n)O(\log n) 条轻边，所以至多被重复遍历 log⁡n\log n 次。时间复杂度为 O(nlog⁡n)O(n\log n)。

以一道例题进行说明。

例 U41492 树上数颜色

题意：

给定一棵 nn 个结点的树，每个结点有一种颜色，每次询问子树颜色种类数。

题解：

不同子树间的答案是互不影响的。所以，在遍历子树结束后，要清除它的影响才能遍历下一棵子树。但是，最后一棵子树的信息是可以保留的。自然，我们希望它是最大的那棵子树，即重子树。

具体地，我们先进行一遍dfs，求出每个结点的重儿子，同时求出dfs序。在统计答案时，我们仿照上面的思路。不过最后一次遍历可以利用dfs序，这样就免去了递归。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int tot,dfn,l[maxn],r[maxn],node[maxn],big[maxn],siz[maxn];
int col[maxn],cnt[maxn],ans[maxn];
vector<int> g[maxn];
void add(int u)
{
    if(cnt[col[u]]==0) tot++;
    cnt[col[u]]++;
}
void del(int u)
{
    cnt[col[u]]--;
    if(cnt[col[u]]==0) tot--;
}
void dfs0(int u,int fa)
{
    l[u]=++dfn;
    node[dfn]=u;
    siz[u]=1;
    for(auto v:g[u])
    {
        if(v==fa) continue;
        dfs0(v,u);
        siz[u]+=siz[v];
        if(!big[u]||siz[big[u]]<siz[v]) big[u]=v;
    }
    r[u]=dfn;
}
void dfs1(int u,int fa,bool keep)
{
    for(auto v:g[u])
    {
        if(v!=fa&&v!=big[u])
            dfs1(v,u,0);
    }
    if(big[u]) dfs1(big[u],u,1);
    for(auto v:g[u])
        if(v!=fa&&v!=big[u])
        {
            for(int i=l[v];i<=r[v];i++) add(node[i]);
        }
    add(u);
    ans[u]=tot;
    if(!keep)
    {
        for(int i=l[u];i<=r[u];i++) del(node[i]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    for(int i=1;i<=n;i++) cin>>col[i];
    dfs0(1,0);
    dfs1(1,0,1);
    int q;cin>>q;
    while(q--)
    {
        int x;cin>>x;
        cout<<ans[x]<<'\n';
    }
    return 0;
}

CF600E Lomsat gelral

题意：

给定一棵 nn 个结点的树。每个结点有颜色 cic_i。如果一种颜色在 xx 的子树内出现次数最多，称其在 xx 子树内为主导色。一棵子树可能有多个主导色。现在，需要求出每棵子树的主导色之和。

数据范围：n≤105,ci≤nn\leq 10^5,c_i\leq n。

题解：

和上一题类似。需要改变的只是每个点对全局信息的影响。添加是容易的，分该颜色出现次数等于或大于当前出现次数最多的颜色即可。但是删除似乎有些麻烦，当一个点被删除后主导色可能发生变化。但事实上，这种麻烦是不必要的。因为当删除时，删除的是整棵子树的信息。所以，直接清空就行了。

代码：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int mx,dfn,l[maxn],r[maxn],node[maxn],big[maxn],siz[maxn];
int col[maxn],cnt[maxn];
ll sum,ans[maxn];
vector<int> g[maxn];
void add(int u)
{
    cnt[col[u]]++;
    if(cnt[col[u]]==mx) sum+=col[u];
    if(cnt[col[u]]>mx) mx=cnt[col[u]],sum=col[u];
}
void del(int u)
{
    cnt[col[u]]--;
}
void dfs0(int u,int fa)
{
    l[u]=++dfn;
    node[dfn]=u;
    siz[u]=1;
    for(auto v:g[u])
    {
        if(v==fa) continue;
        dfs0(v,u);
        siz[u]+=siz[v];
        if(!big[u]||siz[big[u]]<siz[v]) big[u]=v;
    }
    r[u]=dfn;
}
void dfs1(int u,int fa,bool keep)
{
    for(auto v:g[u])
    {
        if(v!=fa&&v!=big[u])
            dfs1(v,u,0);
    }
    if(big[u]) dfs1(big[u],u,1);
    for(auto v:g[u])
        if(v!=fa&&v!=big[u])
        {
            for(int i=l[v];i<=r[v];i++) add(node[i]);
        }
    add(u);
    ans[u]=sum;
    if(!keep)
    {
        for(int i=l[u];i<=r[u];i++) del(node[i]);
        mx=sum=0;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>col[i];
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    dfs0(1,0);
    dfs1(1,0,1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
    return 0;
}

CF570D Tree Requests

题意：

给定一个以 11 为根的 nn 个结点的树，每个点上有一个字母，每个点的深度定义为该节点到 1号结点路径上的点数。mm 次询问，每次询问 a,ba,b 查询以 aa 为根的子树内深度为 bb 的结点上的字母重新排列之后是否能构成回文串。

数据范围：1≤n,m≤5×1051\leq n,m\leq 5\times 10^5。

题解：和上面思路差不多，没啥好写的。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int dfn,l[maxn],r[maxn],node[maxn],big[maxn],siz[maxn];
int a[maxn],b[maxn];
map<pair<int,int>,bool> mp;
vector<int> vec[maxn];
int d[maxn],cnt[maxn][26];
char ch[maxn];
vector<int> g[maxn];
void add(int u)
{
    cnt[d[u]][ch[u]-'a']++;
}
void del(int u)
{
    cnt[d[u]][ch[u]-'a']++;
}
void dfs0(int u,int fa)
{
    l[u]=++dfn;
    node[dfn]=u;
    siz[u]=1;
    d[u]=d[fa]+1;
    for(auto v:g[u])
    {
        if(v==fa) continue;
        dfs0(v,u);
        siz[u]+=siz[v];
        if(!big[u]||siz[big[u]]<siz[v]) big[u]=v;
    }
    r[u]=dfn;
}
void dfs1(int u,int fa,bool keep)
{
    for(auto v:g[u])
    {
        if(v!=fa&&v!=big[u])
            dfs1(v,u,0);
    }
    if(big[u]) dfs1(big[u],u,1);
    for(auto v:g[u])
        if(v!=fa&&v!=big[u])
        {
            for(int i=l[v];i<=r[v];i++) add(node[i]);
        }
    add(u);
    for(auto i:vec[u])
    {
        int ok=0;
        for(int j=0;j<26;j++)
            if(cnt[i][j]&1) ok++;
        mp[{u,i}]=(ok<=1?1:0);
    }
    if(!keep)
    {
        for(int i=l[u];i<=r[u];i++) del(node[i]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=2;i<=n;i++)
    {
        int x;cin>>x;
        g[x].push_back(i),g[i].push_back(x);
    }
    for(int i=1;i<=n;i++) cin>>ch[i];
    for(int i=1;i<=m;i++) 
    {
        cin>>a[i]>>b[i];
        vec[a[i]].push_back(b[i]);
    }
    dfs0(1,0);
    dfs1(1,0,1);
    for(int i=1;i<=m;i++) cout<<(mp[{a[i],b[i]}]?"Yes":"No")<<'\n';
    return 0;
}

CF246E Blood Cousins Return

题意：

给出一棵有 nn 个结点的树。每个结点有一个名字，长度不超过 2020 个字符。mm 次询问，每次询问 (v,k)(v,k) 表示以 vv 为根的子树内深度为 kk 的结点有多少种不同的名字。

数据范围：1≤n,m≤1051\leq n,m\leq 10^5。

题解：

本题和上一题的区别在于深度变成了相对深度。这也是容易处理的，对于每个询问，我们用 dv+kd_v+k 就得到了真实深度。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int dfn,l[maxn],r[maxn],node[maxn],big[maxn],siz[maxn];
string a[maxn];
int d[maxn],ans[maxn];
vector<int> g[maxn];
set<string> s[maxn];
struct query
{
    int id,k;
};
vector<query> q[maxn];
void add(int u)
{
    s[d[u]].insert(a[u]);
}
void del(int u)
{
    s[d[u]].erase(a[u]);
}
void dfs0(int u,int fa)
{
    l[u]=++dfn;
    node[dfn]=u;
    siz[u]=1;
    if(~fa) d[u]=d[fa]+1;
    for(auto v:g[u])
    {
        if(v==fa) continue;
        dfs0(v,u);
        siz[u]+=siz[v];
        if(!big[u]||siz[big[u]]<siz[v]) big[u]=v;
    }
    r[u]=dfn;
}
void dfs1(int u,int fa,bool keep)
{
    for(auto v:g[u])
    {
        if(v!=fa&&v!=big[u])
            dfs1(v,u,0);
    }
    if(big[u]) dfs1(big[u],u,1);
    for(auto v:g[u])
        if(v!=fa&&v!=big[u])
        {
            for(int i=l[v];i<=r[v];i++) add(node[i]);
        }
    add(u);
    for(auto i:q[u])
    {
        int id=i.id,k=i.k;
        if(d[u]+k<maxn) ans[id]=(int)s[d[u]+k].size();
    }
    if(!keep)
    {
        for(int i=l[u];i<=r[u];i++) del(node[i]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        string s;int x;
        cin>>s>>x;
        a[i]=s;
        g[x].push_back(i),g[i].push_back(x);
    }
    int m;cin>>m;
    for(int i=1;i<=m;i++) 
    {
        int x,k;cin>>x>>k;
        q[x].push_back({i,k});
    }
    dfs0(0,-1);
    dfs1(0,-1,1);
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}

CF208E Blood Cousins

题意：

给定一棵 nn 个结点的树。定义一个结点的 pp 级表亲为和它具有相同 pp 级祖先的结点数。给出 mm 次询问，每次询问一个结点的 pp 级表亲有多少个。

数据范围：1≤n,m≤1051\leq n,m\leq 10^5。

题解：

就是求一下每个结点的 pp 级祖先的子树内有多少深度为 pp 的结点。利用倍增预处理一下每个结点的祖先，剩下的和上一题一样。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
vector<int> g[maxn];
int d[maxn],f[maxn][20],lg[maxn];
int dfn,l[maxn],r[maxn],node[maxn],big[maxn],siz[maxn];
int cnt[maxn],ans[maxn];
struct Q
{
    int id,k;
};
vector<Q> q[maxn];
void dfs0(int u,int fa)
{
    l[u]=++dfn;
    node[dfn]=u;
    siz[u]=1;
    f[u][0]=fa;
    for(int i=1;i<=lg[d[u]];i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(auto v:g[u])
    {
        if(v==fa) continue;
        d[v]=d[u]+1;
        dfs0(v,u);
        siz[u]+=siz[v];
        if(!big[u]||siz[big[u]]<siz[v]) big[u]=v;
    }
    r[u]=dfn;
}
int query(int u,int k)
{
    for(int i=20;i>=0;i--)
        if(k>>i&1)
        {
            u=f[u][i];
        }
    return u;
}
void add(int u)
{
    cnt[d[u]]++;
}
void del(int u)
{
    cnt[d[u]]--;
}
void dfs1(int u,int fa,bool keep)
{
    for(auto v:g[u])
    {
        if(v!=fa&&v!=big[u])
            dfs1(v,u,0);
    }
    if(big[u]) dfs1(big[u],u,1);
    for(auto v:g[u])
        if(v!=fa&&v!=big[u])
        {
            for(int i=l[v];i<=r[v];i++) add(node[i]);
        }
    add(u);
    for(auto i:q[u])
    {
        int id=i.id,k=i.k;
        if(d[u]+k<maxn) ans[id]=cnt[d[u]+k]-1;
    }
    if(!keep)
    {
        for(int i=l[u];i<=r[u];i++) del(node[i]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        g[x].push_back(i),g[i].push_back(x);
    }
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    dfs0(0,-1);
    int m;cin>>m;
    for(int i=1;i<=m;i++)
    {
        int v,p;cin>>v>>p;
        int u=query(v,p);
        if(u<1) ans[i]=0;
        else q[u].push_back({i,p});
    }
    dfs1(0,-1,1);
    for(int i=1;i<=m;i++) cout<<ans[i]<<" \n"[i==m];
    return 0;
}

*CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

题意：

给定一棵 nn 个结点的树。每条边上有一个字符（a~v)。一条路径被称为关键路径当且仅当路径上的字符重排后可以成为一个回文串。求每个子树中最长的关键路径。

题解：

考虑状态压缩，将 22 个字符压缩为一个 22 位的二进制数。记 mskimsk_i 表示从根到该点每个字符模 2 意义下出现的次数。那么路径 (u,v)(u,v) 是关键路径当且仅当 msku⊕mskvmsk_u\oplus msk_v 至多有 1 位为 1。

一个结点 uu 的答案由两部分，一种是不经过 uu 的路径。它可以由子结点的 ans 得到。另一种是经过 uu 的，我们需要确保两端点在两棵不同的子树内。所以我们在访问完一棵子树后，才能加入它的信息。

具体地，我们需要维护 mxxmx_x 表示满足 msk=xmsk=x 的结点的最大深度。然后对于每个点，枚举合法的情况，转移一下就可以了。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
const int maxm=(1<<22)+5;
struct edge
{
    int v,w;
};
vector<edge> g[maxn];
int dfn,l[maxn],r[maxn],node[maxn],big[maxn],siz[maxn];
int d[maxn],msk[maxn],mx[maxm],ans[maxn];
void dfs0(int u,int fa)
{
    l[u]=++dfn;
    node[dfn]=u;
    siz[u]=1;
    for(auto i:g[u])
    {
        int v=i.v,w=i.w;
        if(v==fa) continue;
        d[v]=d[u]+1;
        msk[v]=msk[u]^w;
        dfs0(v,u);
        siz[u]+=siz[v];
        if(!big[u]||siz[big[u]]<siz[v]) big[u]=v;
    }
    r[u]=dfn;
}
void add(int u)
{
    mx[msk[u]]=max(mx[msk[u]],d[u]);
}
void del(int u)
{
    mx[msk[u]]=0;
}
void dfs1(int u,int fa,bool keep)
{
    for(auto i:g[u])
    {
        int v=i.v;
        if(v!=fa&&v!=big[u])
        {
            dfs1(v,u,0);
            ans[u]=max(ans[u],ans[v]);
        }
    }
    if(big[u]) 
    {
        dfs1(big[u],u,1);
        ans[u]=max(ans[u],ans[big[u]]);
    }
    if(mx[msk[u]]) ans[u]=max(ans[u],mx[msk[u]]-d[u]);
    for(int i=0;i<22;i++)
        if(mx[msk[u]^(1<<i)]) ans[u]=max(ans[u],mx[msk[u]^(1<<i)]-d[u]);
    add(u);
    for(auto _:g[u])
    {
        int v=_.v;
        if(v!=fa&&v!=big[u])
        {
            for(int i=l[v];i<=r[v];i++)
            {
                if(mx[msk[node[i]]]) ans[u]=max(ans[u],mx[msk[node[i]]]+d[node[i]]-2*d[u]);
                for(int j=0;j<22;j++)
                    if(mx[msk[node[i]]^(1<<j)])
                    {
                        ans[u]=max(ans[u],mx[msk[node[i]]^(1<<j)]+d[node[i]]-2*d[u]);
                    }            
            }
        }
        if(v!=fa&&v!=big[u])
        {
            for(int i=l[v];i<=r[v];i++) add(node[i]);
        }
    }
    if(!keep)
    {
        for(int i=l[u];i<=r[u];i++) del(node[i]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=2;i<=n;i++)
    {
        int x;char ch;cin>>x>>ch;
        int w=1<<(ch-'a');
        g[i].push_back({x,w}),g[x].push_back({i,w});
    }
    dfs0(1,0);
    dfs1(1,0,1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
    return 0;
}
ACM
#树上启发式合并
树上启发式合并
https://je3ter.github.io/2023/07/06/ACM/树上启发式合并/
作者
Je3ter
发布于
2023年7月6日
许可协议