CF375D - Tree and Queries (모 팀 + 횟수 에 따라 블록)

제목: n 개의 결점 을 가 진 나무 한 그루 를 주 고 결점 마다 색깔 c i 가 있다.q 회 묻 기, 매번 v 결점 을 뿌리 로 하 는 서브 트 리 중 출현 횟수 ≥ k 의 색깔 이 몇 가지 가 있 는 지 묻는다.나무의 뿌리 노드 는 1 이다.데이터 범위: 2 < = n < = 1e5 1 < = m < = 1e5 1 < = a [i] < = 1e5;
사고: 매번 k 값 이 다 르 기 때문에 모 팀 을 제외 하고 데이터 구조 유지 횟수 도 있어 야 하고 cnct [] 배열 로 유지 해 야 합 니 다.매번 많이 수정 할 때마다 조 회 는 m 회 밖 에 없다.그러므로 블록 을 나누다.20 분 디 버 깅 완료 2 시간 TT 는 반드시 생각 이 또렷 해 야 한다!!!자살한다.

#include
#include
#include
#include
#define m(a,b) memset(a,b,sizeof a)
#define foru(i,a,b) for(int i=a;i<=b;++i)
#define en '
'
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e5+5;
template<class T>void rd(T &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9')  {f|=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return;
}
struct Edge{int to,nex;}edge[N<<1];
int head[N],tot,sz,in[N],out[N],vis[N],fp[N];
void add(int from,int to)
{
    edge[++tot]=(Edge){to,head[from]};head[from]=tot;
    edge[++tot]=(Edge){from,head[to]};head[to]=tot;
}
void dfs(int x)
{
    vis[x]=1,in[x]=sz++,fp[in[x]]=x;
    for(int i=head[x];i;i=edge[i].nex)
        if(!vis[edge[i].to]) dfs(edge[i].to);
    out[x]=sz-1;
}
int tag[N],sum[320],bl[N],block,n;
void update(int x,int val)
{
    tag[x]+=val;
    sum[bl[x]]+=val;
}
int query(int x)
{
    int ans=0;
    for(int i=x;i<=min(bl[x]*block,n);i++)
        if(tag[i]) ans+=tag[i];//        ???     ans++,   ans+=tag[i].
    for(int i=bl[x]+1;i<=bl[n];i++)
        ans+=sum[i];
    return ans;
}
struct Query{int id,l,r,v;}q[M];
int dexl,dexr,ans[M],cnt[N];
int a[N];
int cmp(Query x,Query y)
{
    if(x.l/block==y.l/block)
        return x.r<y.r;
    return x.l/block<y.l/block;
}
void add(int x){
    x=a[fp[x]];//x   , dfs          .
    if(cnt[x])
        update(cnt[x],-1);//              
    ++cnt[x];
    update(cnt[x],1);
}
void del(int x){
    x=a[fp[x]];
    update(cnt[x],-1);
    --cnt[x];
    if(cnt[x])
        update(cnt[x],1);
}
int main()
{
    int m;rd(n),rd(m);block=sqrt(n);
    foru(i,1,n)
        rd(a[i]),bl[i]=(i-1)/block+1;
    foru(i,1,n-1)
    {
        int x,y;rd(x),rd(y);
        add(x,y);
    }
    sz=1,dfs(1),--sz;
    foru(i,1,m)
    {
        int x,v;rd(x),rd(v);
        q[i]=(Query){i,in[x],out[x],v};
    }
    sort(q+1,q+m+1,cmp);
    dexl=1,dexr=0;
    foru(i,1,m)
    {
        while(dexr<q[i].r) add(++dexr);
        while(dexl>q[i].l) add(--dexl);
        while(dexr>q[i].r) del(dexr--);
        while(dexl<q[i].l) del(dexl++);
        if(q[i].v>n)//       !!!  x=q[i].v>n :bl[x]    ,    RE，      for(int i=bl[x]+1;i<=bl[n];i++)       。
            ans[q[i].id]=0;
        else
            ans[q[i].id]=query(q[i].v);
    }
    for(int i=1;i<=m;i++)
        printf("%d
",ans[i]);
}