题意：

给出一棵树，每个顶点都有权值，现在要你找出满足要求的点对(u,v)数，u是v的祖先并且a[u]*a[v]<=k。

 

思路：

转化一下，a[v]<=k/a[u]，k/a[u]的最大值也就是k/a[v]，也就是寻找<=k/a[v]的个数，到这儿，是不是很像树状数组？

我们只需要从根开始dfs，插入到树状数组中，并且查询即可。注意这道题目需要离散化一下。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 const int INF=0x3f3f3f3f; 8 typedef long long ll; 9 const int maxn=1e6+5;10 11 ll n,k,m;12 ll ans;13 ll a[maxn];14 ll b[maxn];15 ll c[maxn];16 int degree[maxn];17 18 vector
          
            G[maxn];19 20 int lowbit(int x)21 {22 return x&-x;23 }24 25 int sum(int x)26 {27 int ret = 0;28 while(x>0)29 {30 ret+=c[x]; x-=lowbit(x);31 }32 return ret;33 }34 35 void add(int x, int d)36 {37 while(x<=m)38 {39 c[x]+=d;40 x+=lowbit(x);41 }42 }43 44 void dfs(int u, int fa)45 {46 int update_pos=lower_bound(b+1,b+m+1,a[u])-b;47 int query_pos;48 if(a[u]) query_pos=lower_bound(b+1,b+m+1,k/a[u])-b;49 else query_pos=m;50 ans+=sum(query_pos);51 add(update_pos,1);52 for(int i=0;i