先dfs一下把树转换成对应的数组，对每一个询问就相当于求每个区间内出现k次的不同数的个数。然后类似HDOJ3874就可以用树状数组来维护了，运用离线的思想，把询问的区间按右端点排序，再预处理出每个数出现的前一次的位置pre和前k-1次的位置pk。

pre[pre[pk[i]]]<------1---->pre[pk[i]]<----2------>pk[i]<----3------->i

对于i号位置上的数，如果pk[i]存在，则对于右端点是位置i的询问来说如果左端点在2段内，则i位置上的数至少出现了k次（对应树状数组更新（pre[pk[i]]+1,+1) , (pk[i]+1,-1) )。如果在pk之前还有这个数还出现过，也就是说如果询问的左端点落在了1段内，那么这个数出现的次数就大于k了，这个数就不能算了（对应树状数组更新(pre[pre[pk[i]]]+1,-1) , (pre[pk[i]+1,+1)），所以要把数组给更新回来。。。。这样就只要SUM(询问左端点)就是答案。

因为数的大小没有意义，为了方便可以先离散化一下。

『网上好多代码都是错的，可以去Discuss里看一下那组样例』

Boring counting

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 98304/98304 K (Java/Others)
Total Submission(s): 1864 Accepted Submission(s): 522

Problem Description In this problem we consider a rooted tree with N vertices. The vertices are numbered from 1 to N, and vertex 1 represents the root. There are integer weights on each vectice. Your task is to answer a list of queries, for each query, please tell us among all the vertices in the subtree rooted at vertice u, how many different kinds of weights appear exactly K times
Input The first line of the input contains an integer T( T<= 5 ), indicating the number of test cases.
For each test case, the first line contains two integers N and K, as described above. ( 1<= N <= 10 ⁵, 1 <= K <= N )
Then come N integers in the second line, they are the weights of vertice 1 to N. ( 0 <= weight <= 10 ⁹ )
For next N-1 lines, each line contains two vertices u and v, which is connected in the tree.
Next line is a integer Q, representing the number of queries. (1 <= Q <= 10 ⁵)
For next Q lines, each with an integer u, as the root of the subtree described above.
Output For each test case, output "Case #X:" first, X is the test number. Then output Q lines, each with a number -- the answer to each query.

Seperate each test case with an empty line.
Sample Input

Sample Output

Case #1:
1
1
1

Author fish@UESTC_Oblivion
Source 2012 Multi-University Training Contest 6

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; const int maxn=100100; int n,Q,K,val[maxn]; /****************数状数组***********************/ int tree[maxn]; int lowbit(int x) { return x&(-x); } void ADD(int p,int v) { for(int i=p;i<=n;i+=lowbit(i)) tree[i]+=v; } int SUM(int p) { int sum=0; for(int i=p;i;i-=lowbit(i)) sum+=tree[i]; return sum; } /****************前向星*************************/ struct Edge { int to,next; }edge[maxn*2]; int Adj[maxn],Size; void build_init() { Size=0; memset(Adj,-1,sizeof(Adj)); } void Add_Edge(int u,int v) { edge[Size].to=v; edge[Size].next=Adj[u]; Adj[u]=Size++; } /*****************dfs树转数组************************/ int time=1; int ax[maxn]; struct Interval { int l,r; }I[maxn]; void dfs(int x,int fa) { I[x].l=time; for(int i=Adj[x];~i;i=edge[i].next) { int v=edge[i].to; if(v==fa) continue; dfs(v,x); time++; } ax[time]=val[x]; I[x].r=time; } /*******************Lisan*****************************/ int r[maxn],md[maxn],m; bool cmpR(int a,int b) { return val[a]
      
       =1;i--) { if(idx[val[i]]==-1) { int pos=i,cur=K-1; while(pos&&cur) { cur--; pos=pre[pos]; } pk[i]=pos; idx[val[i]]=pk[i]; } else { pk[i]=pre[idx[val[i]]]; idx[val[i]]=pk[i]; } } } int main() { int T,cas=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&K); memset(val,0,sizeof(val)); for(int i=1;i<=n;i++) scanf("%d",&val[i]); build_init(); for(int i=0;i

HDOJ 4358 Boring counting

Boring counting