CodeForces - 375D Tree and Queries （莫队+dfs序+树状数组）

Dear 丶 2021-12-13 16:43 185阅读 0赞

You have a rooted tree consisting of *n* vertices. Each vertex of the tree has some color. We will assume that the tree vertices are numbered by integers from 1 to *n*. Then we represent the color of vertex *v* as *c**v*. The tree root is a vertex with number 1.

In this problem you need to answer to *m* queries. Each query is described by two integers *v**j*, *k**j*. The answer to query *v**j*, *k**j* is the number of such colors of vertices *x*, that the subtree of vertex *v**j* contains at least *k**j* vertices of color *x*.

You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree\_(graph\_theory).

**Input**

The first line contains two integers *n* and *m* (2 ≤ *n* ≤ 105; 1 ≤ *m* ≤ 105). The next line contains a sequence of integers *c*1, *c*2, ..., *c**n* (1 ≤ *c**i* ≤ 105). The next *n* - 1lines contain the edges of the tree. The *i*\-th line contains the numbers *a**i*, *b**i* (1 ≤ *a**i*, *b**i* ≤ *n*; *a**i* ≠ *b**i*) — the vertices connected by an edge of the tree.

Next *m* lines contain the queries. The *j*\-th line contains two integers *v**j*, *k**j* (1 ≤ *v**j* ≤ *n*; 1 ≤ *k**j* ≤ 105).

**Output**

Print *m* integers — the answers to the queries in the order the queries appear in the input.

**Examples**

Input

8 5
    1 2 2 3 3 2 3 3
    1 2
    1 5
    2 3
    2 4
    5 6
    5 7
    5 8
    1 2
    1 3
    1 4
    2 3
    5 3

Output

2
    2
    1
    0
    1

Input

4 1
    1 2 3 4
    1 2
    2 3
    3 4
    1 1

Output

4
    
    题意：
    给定一颗树，树上的每个节点都有一个颜色，以1为根节点。
    每次询问，问以节点v为根节点的子树里面，有多少种颜色出现次数大于k。
    思路：
    想到莫队之后，dfs序和树状数组很好想了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<algorithm>
    #include<vector>
    #include<stack>
    #include<queue>
    #include<map>
    #include<set>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<ctime>
    #define fuck(x) cout<<#x<<" = "<<x<<endl;
    #define debug(a,i) cout<<#a<<"["<<i<<"] = "<<a[i]<<endl;
    #define ls (t<<1)
    #define rs ((t<<1)+1)
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int maxn = 100086;
    const int maxm = 100086;
    const int inf = 2.1e9;
    const ll Inf = 999999999999999999;
    const int mod = 1000000007;
    const double eps = 1e-6;
    const double pi = acos(-1);
    
    int col[maxn];
    int num[maxn];
    int vis[maxn];
    int cnt,Head[maxn];
    int tl[maxn],tr[maxn];
    struct node{
        int v,nxt;
    }e[2*maxn];
    struct query{
        int l,r,id,k;
    }a[maxn];
    
    void add_edge(int u,int v){
        e[cnt].v=v;
        e[cnt].nxt = Head[u];
        Head[u]=cnt++;
    }
    
    void dfs(int u,int fa){
        tl[u]=++cnt;
        num[cnt]=col[u];
        for(int k=Head[u];~k;k=e[k].nxt){
            if(e[k].v!=fa)dfs(e[k].v,u);
        }
        tr[u]=cnt;
    }
    int block;
    bool cmp(query a,query b){
        if(a.l/block!=b.l/block){
           return a.l<b.l;}
        return a.r<b.r;
    }
    int lowbit(int x){
        return x&-x;
    }
    
    int bit[maxn];
    
    int query(int pos){
        int ans=0;
        while(pos){
            ans+=bit[pos];
            pos-=lowbit(pos);
        }
        return ans;
    }
    
    void update(int pos,int val){
        if(pos<=0){
           return;}
        while(pos<maxn){
            bit[pos]+=val;
            pos+=lowbit(pos);
        }
    }
    
    int ans[maxn];
    
    int main()
    {
        memset(Head,-1,sizeof(Head));
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&col[i]);
        }
    
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            add_edge(x,y);
            add_edge(y,x);
        }
        cnt=0;
        dfs(1,0);
    
        block=sqrt(cnt);
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            a[i].l=tl[x];
            a[i].r=tr[x];
            a[i].k=y;
            a[i].id=i;
        }
    
        sort(a+1,a+1+m,cmp);
        int L=1,R=0;
        for(int i=1;i<=m;i++){
            while(L<a[i].l){
                update(vis[num[L]],-1);
                vis[num[L]]--;
                update(vis[num[L]],1);
                L++;
            }
            while(R<a[i].r){
                R++;
                update(vis[num[R]],-1);
                vis[num[R]]++;
                update(vis[num[R]],1);
            }
            while(L>a[i].l){
                L--;
                update(vis[num[L]],-1);
                vis[num[L]]++;
                update(vis[num[L]],1);
            }
            while(R>a[i].r){
                update(vis[num[R]],-1);
                vis[num[R]]--;
                update(vis[num[R]],1);
                R--;
            }
            ans[a[i].id]=query(maxn-1)-query(a[i].k-1);
        }
        for(int i=1;i<=m;i++){
            printf("%d\n",ans[i]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/ZGQblogs/p/10864359.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211213/b27d6752ae8c4565961753a4b46a91d3.png