Boring counting
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 98304/98304 K (Java/Others) Total Submission(s): 2811 Accepted Submission(s): 827
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 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
题目链接:
把DFS序和莫队算法结合了起来,前两发杯具PE,如果用过DFS序配合线段树的话就大概能知道怎么做了,对于一颗子树的询问显然DFS序是很适合的,然后这样就得到了每一个点所管理的区间[L,R],那莫队移动的时候怎么判断是否遇到了某一个原树上的节点呢?显然用先序遍历的方式来得到某一个点管理的区间,那么L这个点必定是子树树根的位置,若这个点管理的位置是[L,R]那么实际上这个子树根点的值就是arr[L],不过由于每一个区间都是满点的,就映射成val[timeorder]=arr[u],其中u是某次dfs时的起点。
除此之外还要判断当前减掉的数字是从k减到k-1还是k+1减到k,加上的同理,最后每一个case之间换一行,结尾不换行Orz……另外最近在玩C++11的匿名函数,在sort里随便用下玩
代码:
#include#include using namespace std;#define INF 0x3f3f3f3f#define CLR(arr,val) memset(arr,val,sizeof(arr))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair pii;typedef long long LL;const double PI=acos(-1.0);const int N=1e5+7;struct edge{ int to; int pre;};struct info{ int l,r; int id,b;};info Q[N];edge E[N];int head[N],tot;int L[N],R[N],order,val[N];int arr[N],cnt[N],ans[N];vector vec;void init(){ CLR(head,-1); tot=0; CLR(L,0); CLR(R,0); order=0; CLR(val,0); CLR(cnt,0); vec.clear();}inline void add(int s,int t){ E[tot].to=t; E[tot].pre=head[s]; head[s]=tot++;}void dfs(const int &now,const int &pre){ L[now]=++order; val[order]=arr[now]; for (int i=head[now]; ~i; i=E[i].pre) { int v=E[i].to; //if(v!=pre) dfs(v,now); } R[now]=order;}int main(void){ int tcase,n,k,i,a,b,m,rt; scanf("%d",&tcase); for (int q=1; q<=tcase; ++q) { init(); scanf("%d%d",&n,&k); for (i=1; i<=n; ++i) { scanf("%d",&arr[i]); vec.push_back(arr[i]); } sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end()); for (i=1; i<=n; ++i) arr[i]=lower_bound(vec.begin(),vec.end(),arr[i])-vec.begin(); for (i=0; i Q[i].l) { --l; ++cnt[val[l]]; if(cnt[val[l]]==k) ++temp; else if(cnt[val[l]]==k+1) --temp; } while (r Q[i].r) { --cnt[val[r]]; if(cnt[val[r]]==k-1) --temp; else if(cnt[val[r]]==k) ++temp; --r; } ans[Q[i].id]=temp; } printf("Case #%d:\n",q); for (i=0; i