昨天教练布置的莫队作业，然后一看我老早就用 DSU on tree 切了，来补题解（

题意

静态树询问子树中，同一种元素的数量不小于 \(k\) 的元素有多少种。

莫队做法

容易观察到子树在 \(\rm DFS\) 序上是一段连续的区间，于是问题就转化成了区间。

维护一个桶来记录有多少种元素在区间中有 \(x\) 个，在更新的时候注意是否等于 \(k\) 即可。

DSU on tree做法

同样维护一个桶，记录同样的东西，判定也是同样的。

所以 DSU on tree 就是复杂度为 Polylog 的莫队？（大雾）

code:（只写了 DSU on tree）

#include<cstdio>

const int M=1e5+5;

int n,m,Son,f[M],siz[M],son[M],col[M],num[M],cnt[M];

struct Edge{

    int to;Edge*nx;

}e[M<<1],*h[M],*qwq=e;

struct Q{

    int k,ans;Q*nx;

}q[M],*t[M],*tot=q+1;

inline void Add(const int&u,const int&v){

    *qwq=(Edge){v,h[u]};h[u]=qwq++;

    *qwq=(Edge){u,h[v]};h[v]=qwq++;

}

void DFS(int u){

    siz[u]=1;

    for(Edge*E=h[u];E;E=E->nx){

        int v=E->to;

        if(v==f[u])continue;

        f[v]=u;DFS(v);siz[u]+=siz[v];

        if(siz[v]>siz[son[u]])son[u]=v;

    }

}

void change(int u,bool keep){

    if(keep)++cnt[++num[col[u]]];

    else --cnt[num[col[u]]--];

    for(Edge*E=h[u];E;E=E->nx){

        int v=E->to;

        if(v==f[u]||v==Son)continue;

        change(v,keep);

    }

}

void Query(int u,bool keep){

    for(Edge*E=h[u];E;E=E->nx){

        int v=E->to;

        if(v==f[u]||v==son[u])continue;

        Query(v,false);

    }

    if(son[u])Query(son[u],true),Son=son[u];

	change(u,true);Son=0;

    for(Q*E=t[u];E;E=E->nx)E->ans=cnt[E->k];

    if(!keep)change(u,false);

}

signed main(){

    register int i,u,v;

    scanf("%d%d",&n,&m);

    for(i=1;i<=n;++i)scanf("%d",col+i);

    for(i=1;i<n;++i)scanf("%d%d",&u,&v),Add(u,v);

    for(i=1;i<=m;++i)scanf("%d%d",&u,&tot->k),tot->nx=t[u],t[u]=tot++;

    DFS(1);Query(1,true);

    for(i=1;i<=m;++i)printf("%d\n",q[i].ans);

}

巴特西

CF375D题解

题意

莫队做法

DSU on tree做法

最新文章

热门文章