Dsu on Tree学习笔记

chen_qian · 2021-02-22 21:07:38 · 题解

一种极为暴力的办法。

当我们在处理静态树上问题时，我们有时会遇见将子树信息合并到父节点上。我们可以对于每一个树上节点都开一个桶来维护。但是可能空间会开不下。

所以我们只能开一个全局桶，每次都要把桶清空，然后暴力统计子树里面所有信息。

这样对于每一个节点，我们都需要将其所有子树的所有节点全部遍历，可能会有超时风险。

但是我们发现，在用dfs进行遍历时，我们可以优先计算子节点再计算父节点，这就意味着对于每个节点x,我们都可以保留一个子树y的信息，让其直接继承到x的信息，这样，选那一个子树就成为了我们要解决的问题。

一个很简单的贪心是，我们选节点数最多的那个，这样继承到的信息更多，节省的时间也就越多。

那么就有一个类似重链剖分的操作。遍历整棵树，并记录下他的重儿子。

那么接下来就是暴力的思路了，具体实现看一个例题。

一棵有根树，以1为根。每个点只有一个颜色，请你求出每个点的子树的出现次数最多的颜色。有多个颜色出现次数相同时，输出最小的解。

来源：bsoj6750

本题我们直接开一个桶t[x]表示子树中颜色为x的个数，然后在找到重儿子的情况下，对于每一个节点我们重复以下步骤。

优先递归计算非重子节点信息
计算重子节点信息
再次递归计算非重子节点信息，并将信息合并到重子节点的信息
加入当前节点的信息，更新答案
加入当前节点不是父节点重子节点，清空桶

#include<bits/stdc++.h>
#define N 300005
using namespace std;
int n,w[N],size[N],tmp[N],son[N];
int head[N],idx,t[N],seg[N],rev[N],cnt,fs[N],MAXN;
int ans[N];
struct edge{
    int v,next;
}e[2*N];
void add(int u,int v){
    e[++idx].v=v;
    e[idx].next=head[u];
    head[u]=idx;
}
void dfs1(int x,int f){
    size[x]=1;
    seg[x]=++cnt;//类似树链剖分的操作 
    rev[cnt]=x;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(y==f) continue;
        dfs1(y,x);
        size[x]+=size[y];
        if(size[y]>size[son[x]]) son[x]=y;
    }
}
void dfs2(int x,int f,int type){//type表示x是不是重儿子 
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(y==son[x]||y==f) continue;
        dfs2(y,x,1);
    }
    if(son[x]) dfs2(son[x],x,0);
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(y==f||y==son[x]) continue;
        for(int j=seg[y];j<=seg[y]+size[y]-1;j++) t[w[rev[j]]]++;//遍历子树 
    }
    t[w[x]]++;
//  cout<<x<<": ";
//  for(int i=1;i<=MAXN;i++) cout<<t[i]<<' ';
//  cout<<endl;
    int mx=0;
    for(int i=1;i<=MAXN;i++){
        if(t[i]>mx){
            mx=t[i];
            ans[x]=i;
        }
    }
    if(type) for(int i=1;i<=MAXN;i++) t[i]=0;//清零计数数组 
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
        tmp[i]=w[i];
    }
    sort(tmp+1,tmp+n+1);
    int len=unique(tmp+1,tmp+n+1)-tmp-1;
    for(int i=1;i<=n;i++){
        int tmpp=lower_bound(tmp+1,tmp+len+1,w[i])-tmp;
        fs[tmpp]=w[i];
        w[i]=tmpp;
        MAXN=max(tmpp,MAXN);
        //cout<<w[i]<<' ';
    }
    //cout<<endl;
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs1(1,0);
    dfs2(1,0,1);
    for(int i=1;i<=n;i++) printf("%d\n",fs[ans[i]]);
    return 0;
}

CF375D

本题同样也是类似上题的问题。

只需额外计算d[k]表示子树中出现数量大于等于k的颜色的个数。

但是这样来想似乎就需要计算前缀和了？

实际上不用，对于一个出现k次的颜色，他只对于d[i],i<=k的答案有贡献，而我们得到k这个答案时，是从0依次加上来的那么我们只需每加一次就将答案+1即可。

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m;
int head[N],idx,c[N];
int t[N],size[N],son[N];
bool vis[N];
struct query{
    int k,id; 
};
int ans[N],d[N];
struct edge{
    int v,next;
}e[N<<1];
vector<query> q[N];
void add(int u,int v){
    e[++idx].v=v;
    e[idx].next=head[u];
    head[u]=idx;
}
void dfs1(int x,int f){
    size[x]=1;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(y==f) continue;
        dfs1(y,x);
        size[x]+=size[y];
        if(size[y]>size[son[x]]) son[x]=y;
    }
}
void solve(int x,int f,int p){
    if(p==-1)
        d[t[c[x]]]+=p;
    t[c[x]]+=p;
    if(p==1)
        d[t[c[x]]]+=p;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(y==f||vis[y])
            continue;
        solve(y,x,p);
    }
}
void dfs2(int x,int f,int type){
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(y==f||y==son[x]) continue;
        dfs2(y,x,1);
    }
    if(son[x]){
        dfs2(son[x],x,0);
        vis[son[x]]=1;
    }
    solve(x,f,1);
    //for(int i=1;i<=10;i++) cout<<d[i]<<' ';
    //cout<<endl;
    for(int i=0;i<q[x].size();i++)
        ans[q[x][i].id]=d[q[x][i].k];
    if(son[x]) vis[son[x]]=0;
    if(type) solve(x,f,-1);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=m;i++){
        int u;
        query x;
        scanf("%d%d",&u,&x.k);
        x.id=i;
        q[u].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,0,1);
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

注意本题我们用到了离线算法，另外这里我是用递归实现的计数与清空

CF570D

显然我们可以知道的是假如说一串字符重拍后能够成回文串，那么其至多有一个出现奇数次的字符。

再加上体面说的深度k是对于统一的根节点1来讲的，那么很容易想到的t[x]来进行状态压缩，t[x]的二进制下的i位为0表示字母i出现偶数次，否则出现奇数次。

然后用check()来计算出现了几个出现奇数次的字母。

#include<bits/stdc++.h>
#define N 500005
using namespace std;
int n,m;
int head[N],idx,w[N];
int size[N],son[N],dep[N];
int t[N];
bool vis[N],ans[N];
struct query{
    int k,id; 
};
struct edge{
    int v,next;
}e[N<<1];
vector<query> q[N];
void add(int u,int v){
    e[++idx].v=v;
    e[idx].next=head[u];
    head[u]=idx;
}
void dfs1(int x,int f){
    size[x]=1;
    dep[x]=dep[f]+1;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        dfs1(y,x);
        size[x]+=size[y];
        if(size[y]>size[son[x]]) son[x]=y;
    }
}
bool check(int x){
    bool f=0;
    while(x){
        if(x&1){
            if(f==1) return false;
            f=1;
        }
        x>>=1;
    }
    return true;
}
void solve(int x){
    t[dep[x]]^=(1<<w[x]);
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(vis[y]) continue;
        solve(y);
    }
}
void dfs2(int x,int type){
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(y==son[x]) continue;
        dfs2(y,1);
    }
    if(son[x]){
        dfs2(son[x],0);
        vis[son[x]]=1;
    }
    solve(x);
    for(int i=0;i<q[x].size();i++) ans[q[x][i].id]=check(t[q[x][i].k]);
    if(son[x]) vis[son[x]]=0;
    if(type) solve(x);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++){
        int f;
        scanf("%d",&f);
        add(f,i); 
    }
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
        w[i+1]=s[i]-'a';
    for(int i=1;i<=m;i++){
        int u;
        query x;
        scanf("%d%d",&u,&x.k);
        x.id=i;
        q[u].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=m;i++){
        if(ans[i]==1) puts("Yes");
        else puts("No");
    }
    return 0;
}