HDU 5877 Weak Pair（树状数组）

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

 

【题目大意】

 　　给出一棵带权有根树，询问有几对存在祖先关系的点对满足权值相乘小于等于k。

【题解】

　　我们沿根节点开始将点权加入权值树状数组，每次处理完子树就回溯，保证每个节点的答案统计是在只包括祖先节点的树状数组中进行。

【代码】

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N=100005;
long long a[N],disc[N],k;
int c[N],ans,b[N],d[N],T,n;
vector<int> v[N];
int add(int x,int num){while(x<N)c[x]+=num,x+=x&-x;}
int query(int x){int s=0;while(x)s+=c[x],x-=x&-x;return s;}
int remark(long long x){
      int l=1,r=n;
      while(l<=r){
            int mid=(l+r)>>1;
            if(disc[mid]<x)l=mid+1;
            else if(disc[mid]==x)return mid;
            else r=mid-1;
      }
}
void dfs(int x){
    add(b[x],1);
    for(int i=0;i<v[x].size();i++)dfs(v[x][i]);
    long long t=k/a[x];
    int u=upper_bound(disc+1,disc+n+1,t)-disc-1;
    add(b[x],-1);
      ans+=query(u);
}
int main(){
    scanf("%d",&T);
    while(T--){
        memset(d,0,sizeof(d));
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)v[i].clear();
        scanf("%d%lld",&n,&k);
        for(int i=1;i<=n;i++)scanf("%lld",a+i),disc[i]=a[i];
        sort(disc+1,disc+n+1);
        for(int i=1;i<=n;i++)b[i]=remark(a[i]);
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            d[y]++;
        }ans=0;
        for(int i=1;i<=n;i++)if(!d[i])dfs(i);
        printf("%d
",ans);
    }return 0;
}