HDU 5877 Weak Pair（树状数组）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5877
【题目大意】
给出一棵带权有根树，询问有几对存在祖先关系的点对满足权值相乘小于等于k。
【题解】
我们沿根节点开始将点权加入权值树状数组，每次处理完子树就回溯，保证每个节点的答案统计是在只包括祖先节点的树状数组中进行。
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #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\n",ans); }return 0;} |
评论 (0)
