本文共 4713 字，大约阅读时间需要 15 分钟。

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 5, 1 <= K <= N ) Then come N integers in the second line, they are the weights of vertice 1 to N. ( 0 <= weight <= 10 9 ) 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 5) 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 1 3 1 1 2 2 1 2 1 3 3 2 1 3 Sample Output Case #1: 1 1 1 这个题和eduoj3307的题目一样的，但是这个题需要树形转换成线性的。 离散化，树形转化为数组的线性结构，离线做法，树状数组，排序后边插入边询问等多种处理技巧。 因为这个题目数据量比较大，需要离散化一下。 .在插入到某点i是，第k(1<=k<=i)表示k到i的答案，要明白：

每插入新的一点，改变的只有插入的这个数，设这个数P出现的位置是P0,P1,P2…Pj-k-1,Pj-k,Pj-k+1…Pj-1，

如果询问的左端点在(Pj-k-1,Pj-k]，右端点在i，P就凑够K次

现在在Pj=i插入新的数P，就变成如果询问的左端点在(Pj-k,Pj-k+1]，P凑够K次，

而左端点在(Pj-k-1,Pj-k]的P出现的次数变成K+1，不是答案，

所以树状数组的操作是(Pj-k-1,Pj-k] 区间-1，(Pj-k,Pj-k+1]区间+1，然后询问左端点的值就好了（因为树状数组上第k位表示k到i的答案）

可见要用到的操作：区间更新，单点询问，用第二类树状数组 代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=1e5+100;struct node{
   	int l;	int r;	int id;	bool operator<(const node &a)const{
   		return a.r>r;	}}b[maxx];struct Node{
   	int to,next;}e[maxx<<1];vector
    
      v[maxx];int head[maxx<<1],in[maxx],out[maxx],a[maxx],pre[maxx];ll c[maxx],ans[maxx];int n,m,k,tot,sign;/*-------------事前准备--------------*/ inline void init(){
   	memset(head,-1,sizeof(head));	memset(c,0,sizeof(c));	tot=sign=0;}inline void add(int u,int v){
   	e[tot].to=v,e[tot].next=head[u],head[u]=tot++;}/*---------------dfs---------------*/inline void dfs(int u,int f){
   	in[u]=++sign;	pre[sign]=a[u];	for(int i=head[u];i!=-1;i=e[i].next)	{
   		int to=e[i].to;		if(to==f) continue;		dfs(to,u);	}	out[u]=sign;}/*------------树状数组------------*/inline int lowbit(int x){
   return x&-x;}inline void update(int cur,int v){
   while(cur<=maxx) c[cur]+=v,cur+=lowbit(cur);}inline ll query(int cur){
   int sum=0;while(cur>0) sum+=c[cur],cur-=lowbit(cur);return sum;}int main(){
   	int t,kk=0,x,y;	scanf("%d",&t);	while(t--)	{
   		scanf("%d%d",&n,&k);		init();map
     
       mp;		int cnt=0;		for(int i=1;i<=n;i++) 		{
   			scanf("%d",&a[i]);			if(mp[a[i]]==0)			{
   				mp[a[i]]=++cnt;				a[i]=cnt;				v[cnt].clear();				v[cnt].push_back(0);			}			else a[i]=mp[a[i]];		}		for(int i=1;i
      
       =k)			{
   				if(y>k)//出现次数大于k次了，就需要把之前的标记取消掉，类似于统计区间数字的操作。				{
   					update(v[x][y-k-1]+1,-1);					update(v[x][y-k]+1,1);				}				update(v[x][y-k]+1,1);//增加新的标记				update(v[x][y-k+1]+1,-1);			}			while(b[j].r==i&&j<=m) ans[b[j].id]=query(b[j++].l);		}		printf("Case #%d:\n",++kk);		for(int i=1;i<=m;i++) printf("%d\n",ans[i]);		if(t) puts("");	}}
      
     
    
   

eduoj的题目链接：

这是统计区间出现次数为两次的数字个数 代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=5e5+100;struct Node{
   	int l;	int r;	int id;	bool operator <(const Node &a)const{
   		return a.r>r;	}}e[maxx];int a[maxx],c[maxx],ans[maxx];vector
    
      v[maxx];int n,m;/*-------------树状数组-------------*/int lowbit(int x){
   	return x&(-x);}void update(int x,int val){
   	for(int i=x;i<=n;i+=lowbit(i))		c[i]+=val;}int query(int x){
   	int ans=0;	for(int i=x;i>0;i-=lowbit(i))		ans+=c[i];	return ans;}int main(){
   	while(~scanf("%d%d",&n,&m))	{
   		int cnt=0,len;		map
     
       mp;		memset(c,0,sizeof(c));		for(int i=1;i<=n;i++) 		{
   			scanf("%d",&a[i]);			if(!mp[a[i]]) 			{
   				mp[a[i]]=++cnt;				a[i]=cnt;				v[cnt].clear();				v[cnt].push_back(0);			}			else a[i]=mp[a[i]];		}		for(int i=1;i<=m;i++)		{
   			scanf("%d%d",&e[i].l,&e[i].r);			e[i].id=i;		}		sort(e+1,e+1+m);		for(int i=1,pos=1;i<=n;i++)		{
   			int u=a[i];			v[u].push_back(i);			int len=v[u].size()-1;			if(len>=2)			{
   				if(len>2)//消除上一次含K个U值的区间更新				{
   					update(v[u][len-3]+1,-1);					update(v[u][len-2]+1,1);				}				update(v[u][len-2]+1,1);				update(v[u][len-1]+1,-1);			}			while(e[pos].r==i)			{
   				ans[e[pos].id]=query(e[pos].l);				pos++;			}			}		for(int i=1;i<=m;i++) printf("%d\n",ans[i]);	}	return 0;}
     
    
   

努力加油a啊，(^o)/~

转载地址：http://oztvi.baihongyu.com/