CF246E Blood Cousins Return(线段树合并套set)题解

发布于 2021-10-19  60 次阅读


题目大意

给你一片 $n$ 个点的森林,每个点有一个字符串作为名字。

有 $m$ 次询问,每次询问一个点 $v_i$ 有多少个不同的名字的 $k_i$ 级儿子。

(一个节点的 $k$ 级儿子即为深度是该节点深度加 $k$ 的儿子节点。)

$1 \le n,m \le 10^5, 1 \le v_i,k_i \le n$。

解题思路

啊这道题名字叫 Blood Cousins Return,而之前的 CF208EBlood Cousins,可以猜想这两题肯定是有关系的(确信)。

事实上还真的有关系,不过关系不大。不会 CF208E 的可以去看我的博客

跟深度有关的问题,线段树合并几乎是万能的。考虑线段树合并,我们只要在每个线段树节点上开个 std::set ,维护深度为当前线段树节点代表区间 $l \sim r$ 的点的名字放在一起,再去重后的结果。每次合并线段树节点的时候直接把 $size$ 小的 set 合并到 $size$ 大的 set 上,大概是叫做 set 的启发式合并?

考虑证明复杂度。

我们考虑类似于轻重链剖分的思想,每个点离开自己 set 被合并到其他 set 的次数一定不超过 $O(\log ⁡n)$ 次,因为每次这么做,set 的 $siz$ 至少乘 $2$ 。而在 $siz$ 大的 set 里是直接继承的。加上 set 本身平衡树的复杂度,所以总复杂度是 $O(n \log^2⁡n )$ 的。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=200005,LogN=20;

bool St;

struct Edge{
    int vet,nxt;
}e[N<<1];

struct Ques{
    int val,ord;
};

struct Node{
    int lson,rson;
    set <int> s;
}tree[N*LogN];

int n,m,edge=0,logN=0,head[N];
int fa[N],dep[N],name[N];
int ans[N],rt[N],cntNode=0,cntMap=0;
bool isrt[N];
vector <Ques> q[N];
map <string,int> Map;

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline void addedge(int x,int y){
    e[++edge].vet=y;
    e[edge].nxt=head[x];
    head[x]=edge;
}

inline void dfs(int x,int fath){
    fa[x]=fath; dep[x]=dep[fath]+1;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].vet;
        if (v==fath) continue;
        dfs(v,x);
    }
}

#define lid (tree[id].lson)
#define rid (tree[id].rson)

void pushup(int id){
    if (tree[lid].s.size()>tree[rid].s.size()){
        tree[id].s=tree[lid].s;
        for (auto it : tree[rid].s)
            tree[id].s.insert(it);
    }
    else {
        tree[id].s=tree[rid].s;
        for (auto it : tree[lid].s)
            tree[id].s.insert(it);
    }
}

void Insert(int& id,int l,int r,int x,int val){
    if (!id) id=++cntNode;
    if (l==r){
        tree[id].s.insert(val);
        return void();
    }
    int mid=(l+r)>>1;
    if (x<=mid) Insert(lid,l,mid,x,val);
    else Insert(rid,mid+1,r,x,val);
    pushup(id);
}

int Mergeset(int x,int y){
    if (tree[x].s.size()>tree[y].s.size()){
        for (auto it : tree[y].s)
            tree[x].s.insert(it);
        return x;
    }
    else {
        for (auto it : tree[x].s)
            tree[y].s.insert(it);
        return y;
    }
}

int Merge(int x,int y,int l,int r){
    if (!x) return y;
    if (!y) return x;
    if (l==r) return Mergeset(x,y);
    int mid=(l+r)>>1;
    tree[x].lson=Merge(tree[x].lson,tree[y].lson,l,mid);
    tree[x].rson=Merge(tree[x].rson,tree[y].rson,mid+1,r);
    // pushup(x);
    return x;
}

int Query(int id,int l,int r,int val){
    if ((!id) || (l>r)) return 0;
    if (l==r) return tree[id].s.size();
    int mid=(l+r)>>1;
    if (val<=mid) return Query(lid,l,mid,val);
    else return Query(rid,mid+1,r,val);
}

inline void Dfs(int x,int fath){
    // printf("x=%d fath=%d dep[x]=%d\n",x,fath,dep[x]);
    rt[x]=++cntNode;
    Insert(rt[x],1,n+1,dep[x],name[x]);
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].vet;
        if (v==fath) continue;
        Dfs(v,x);
        rt[x]=Merge(rt[x],rt[v],1,n+1);
    }
    for (auto it : q[x])
        ans[it.ord]=Query(rt[x],1,n+1,it.val);
}

int main(){
    //freopen("CF246E.in","r",stdin);
    //freopen("CF246E.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n; logN=(int)(log2(n)+1);
    for (int i=1;i<=n;++i){
        int x; string str; cin>>str>>x;
        if (Map.find(str)==Map.end()) Map[str]=name[i]=++cntMap;
        else name[i]=Map[str];
        if (x==0){ isrt[i]=true; continue; }
        addedge(x,i);
        addedge(i,x);
    }
    cin>>m;
    for (int i=1;i<=n;++i)
        if (isrt[i]) dfs(i,0);
    for (int i=1;i<=m;++i){
        int x,y; cin>>x>>y;
        q[x].push_back((Ques){dep[x]+y,i});
    }
    for (int i=1;i<=n;++i)
        if (isrt[i]) Dfs(i,0);
    for (int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    bool Ed; cerr<<"MemoryUsed:"<<1.0*(&St-&Ed)/1024/1024<<endl;
    return 0;
}

我们无法选择过去,但我们可以改变未来。