题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4358

题意:以1为根节点含有N(N <= 1e5)个结点的树,每个节点有一个权值(weight <= 1e9)。之后有m(m <= 1e5)次查询,每次查询以节点u为子树的树中,权值出现k次的权值有多少个?

Sample Input
1
3 1 (n,k)
1 2 2
1 2
1 3
3 (m)
2 1 3
 
Sample Output
Case #1:
1
1
1
 
思路:建好树之后,dfs得到L[x],R[x].即将树形结构变成了线性的结构。并且由于问的是权值出现k次的权值有多少个,和权值的大小无关。就可以离散化,在dfs中把节点重新排序,并且重新赋值.(我们只关心dfs序之后的id和val);这样之后直接跑莫队即可;
细节:至于离散化,直接使用了vector和lower_bound()来合并相同的值;之后输入时建好查询的q[]即可.
#pragma comment(linker, "/STACK:1024000000")
#include<bits/stdc++.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define MSi(a) memset(a,0x3f,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
typedef pair<int,int> PII;
#define A first
#define B second
#define MK make_pair
#define pb push_back
typedef __int64 ll;
template<typename T>
void read1(T &m)
{
T x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
if(a>) out(a/);
putchar(a%+'');
}
const int M = ;
int head[M],tot,a[M],dfs_clock;
int T,kase = ,i,j,k,n,m,top,cnt[M];
struct Edge{
int to,w,Next;
Edge(){}
Edge(int to,int w,int Next):to(to),w(w),Next(Next){}
}e[M<<];
inline void ins(int u,int v,int w = )
{
e[++tot] = Edge{v,w,head[u]};
head[u] = tot;
}
vector<int> p;
void init()
{
dfs_clock = tot = ;
MS0(head);p.clear();
MS0(cnt);
}
int L[M],R[M],val[M],ans[M];
void dfs(int u,int pre)
{
L[u] = ++dfs_clock;
val[dfs_clock] = a[u];//关系的只是dfs序之后的序号;
for(int d = head[u];d;d = e[d].Next){
int v = e[d].to;
if(v == pre) continue;
dfs(v,u);
}
R[u] = dfs_clock;
}
struct data{
int l,r,id,block;
data(){}
data(int l,int r,int id,int block):l(l),r(r),id(id),block(block){}
}q[M];
bool cmp(const data& a,const data& b)
{
return a.block - b.block?a.block < b.block:a.r < b.r;
}
void update(int pos,int add)
{
if(cnt[val[pos]] == k) top--;
else if(cnt[val[pos]] + add == k) top++;
cnt[val[pos]] += add;
}
void solve()
{
top = ;
for(int i = ,l = ,r = ;i <= m;i++){
while(r < q[i].r) update(++r,);
while(r > q[i].r) update(r--,-);
while(l < q[i].l) update(l++,-);
while(l > q[i].l) update(--l,);
ans[q[i].id] = top;
}
}
int main()
{
read1(T);
while(T--){
init();
read2(n,k);
rep1(i,,n) read1(a[i]),p.pb(a[i]);
sort(p.begin(),p.end());
rep1(i,,n) //离散化;
a[i] = lower_bound(p.begin(),p.end(),a[i]) - p.begin();
int u,v;
rep0(i,,n){
read2(u,v);
ins(u,v);ins(v,u);
}
dfs(,-);
int block = sqrt(n);
read1(m);
rep1(i,,m){
read1(u);
q[i] = data(L[u],R[u],i,L[u]/block);
}
sort(q+,q++m,cmp);
solve();
if(kase) puts("");
printf("Case #%d:\n",++kase);
rep1(i,,m){
out(ans[i]);
puts("");
}
}
return ;
}

最新文章

  1. [No000076]用Eclipse编写python(配置PyDev插件)
  2. 蓝牙-HCI错误码列表
  3. 专业版Unity技巧分享:使用定制资源配置文件
  4. System.Web.Caching.Cache类 缓存
  5. xml转成数组,原来这么简单!
  6. 一个获取文件绝对路径的sh
  7. 转:CSS选择器笔记
  8. Hanoi汉诺塔问题——递归与函数自调用算法
  9. Jsp敏感词过滤
  10. Kubernetes — 重新认识Docker容器
  11. Centos中安装gitlab
  12. HDU-6060 RXD and dividing
  13. hive metastore &amp;&amp; hiveserver2 . jvm 配置调整优化
  14. Zabbix监控Low level discovery实时监控网站URL状态
  15. Zookeeper —— 初识
  16. NHibernate问题求大神解决!!!
  17. elasticsearch(一) 之 elasticsearch初识
  18. 12-5 张雨RTCM3数据解码解不出的原因
  19. unity的prefab(预设)例子
  20. bingoyes&#39; tiny dream

热门文章

  1. [018]C++ explicit构造函数
  2. [转]详述DHCP服务器的三种IP分配方式
  3. DRM in Android
  4. windows 7 共享,未授予用户在此计算机上的请求登录类型
  5. 我的开发框架(WinForm)4
  6. 学习opencv中文版教程——第二章
  7. [记录]ns_error_unexpected firefox tinymce
  8. 关于post请求参数的大小限制的说明
  9. 电脑小白学习软件开发-C#的选择语句、异常捕获,进攻程序员
  10. Entity Framework 学习整理(分播客整理)