题意：给定一个有根树和k，每个节点权值为ai,求有序点对(u,v)的数量，有序点对需满足：u是v的祖先，且au*av<=k；
题解一：dfs序+主席树
求出树的dfs序，因为一棵子树的所有子节点在dfs序中是连续的，设起始序号为st，结尾序号为ed。那么对于子树的根节点i来说，只需要求[st,ed]这段区间中<=k/a[i]的个数即可，这可以用主席树实现（i点是作为祖先节点统计数量）
ps.处理时要用离散化
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <set> #include <vector> using namespace std; typedef long long LL; const int N=100000+10; struct Tree{ int l,r,s; }T[5000000]; int n,m,S; LL K; vector<int>V[N]; int st[N],ed[N],Time; int a[N],b[N],d[N],Root[N]; int cnt; void WZJ() { for (int i=1;i<=n;i++)b[i]=a[i]; sort(b+1,b+n+1); m=unique(b+1,b+n+1)-(b+1);// for (int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+m+1,a[i])-b;// } void Insert(int&p,int L,int R,int v) { cnt++;T[cnt]=T[p];p=cnt; T[p].s++; if (L==R)return ; int mid=(L+R)>>1; if (v<=mid)Insert(T[p].l,L,mid,v); else Insert(T[p].r,mid+1,R,v); } int Find(int&p,int L,int R,int l,int r) { if (l>r)return 0; if (L==l && R==r)return T[p].s; int mid=(L+R)>>1; if (r<=mid)return Find(T[p].l,L,mid,l,r);else if (mid< l)return Find(T[p].r,mid+1,R,l,r);else{ return Find(T[p].l,L,mid,l,mid)+Find(T[p].r,mid+1,R,mid+1,r); } } int GET(LL v) { if (b[1]>v)return 0; int L=1,R=m,mid,Ans; while (L<=R){ mid=(L+R)>>1; if (b[mid]<=v)Ans=mid,L=mid+1; else R=mid-1; } return Ans; } void dfs(int u) { Time++;st[u]=Time; Root[Time]=Root[Time-1]; Insert(Root[Time],1,m,a[u]); for (int i=0;i<int(V[u].size());i++){ dfs(V[u][i]); } ed[u]=Time; } void work() { scanf("%d",&n);cin>>K; for (int i=1;i<=n;i++)scanf("%d",&a[i]),V[i].clear(); memset(d,0,sizeof d); for (int i=1;i<n;i++){ int u,v;scanf("%d%d",&u,&v); V[u].push_back(v); d[v]++; } WZJ(); for (int i=1;i<=n;i++)if (d[i]==0){S=i;break;} Time=0; Root[0]=0;cnt=0; dfs(S); LL Ans=0; for (int i=1;i<=n;i++){ int bj=GET(K/b[a[i]]); Ans+=Find(Root[ed[i]],1,m,1,bj)-Find(Root[st[i]],1,m,1,bj); } cout<<Ans<<endl; } int main() { //freopen("1.txt","r",stdin); int Case;scanf("%d",&Case); while (Case--)work(); return 0; } 题解二：树状数组dfs时，每遇到一个点，把值插入树状数组；每离开一个点，把值从树状数组中移除。
对于当前搜到的点i，统计树状数组中<=k/a[i]的个数，（i点是作为子孙节点统计数量）
