Weak Pair

                                                                              Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)                                                                                                          Total Submission(s): 3320    Accepted Submission(s): 1016 Problem Description You are given a  rooted  tree of  N  nodes, labeled from 1 to  N . To the  i th node a non-negative value  ai  is assigned.An  ordered  pair of nodes  (u,v)  is said to be  weak if   (1)  u  is an ancestor of  v  (Note: In this problem a node  u  is not considered an ancestor of itself);   (2)  au×av≤k . Can you find the number of weak pairs in the tree?   Input There are multiple cases in the data set.   The first line of input contains an integer  T  denoting number of test cases.   For each case, the first line contains two space-separated integers,  N  and  k , respectively.   The second line contains  N  space-separated integers, denoting  a1  to  aN .   Each of the subsequent lines contains two space-separated integers defining an edge connecting nodes  u  and  v  , where node  u  is the parent of node  v .   Constrains:        1≤N≤105         0≤ai≤109         0≤k≤1018   Output For each test case, print a single integer on a single line denoting the number of weak pairs in the tree.   Sample Input 1 2 3 1 2 1 2   Sample Output 1   Source 2016 ACM/ICPC Asia Regional Dalian Online   Recommend wange2014   题意：给出一棵树，告诉你树上节点的权值，问有多少对（u，v）满足u是v的祖先，且两个节点权值的乘积小于等于k

解题思路：树状数组+离散化

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <queue> #include <vector> #include <bitset> #include <functional> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; int vis[100005 * 2],n; LL a[100005 * 2], b[100005 * 2], ans, k, xx[100005 * 2]; vector<int>g[100005]; LL lowbit(LL x) { return x&(-x); } void add(LL x, int val) { while (x <= 2 * n) { xx[x] += val; x += lowbit(x); } } LL getsum(LL x) { LL sum = 0; while (x>0) { sum += xx[x]; x -= lowbit(x); } return sum; } void dfs(int s) { int Size = g[s].size(); LL sum = getsum(a[n + s]); ans += sum; add(a[s], 1); for (int i = 0; i<Size; i++) { int v = g[s][i]; dfs(v); } add(a[s], -1); } int main() { int t; scanf("%d", &t); while (t--) { ans = 0; memset(vis, 0, sizeof(vis)); memset(xx, 0, sizeof(xx)); for (int i = 0; i <= n; i++) g[i].clear(); scanf("%d%lld", &n, &k); int u, v; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); a[i + n] = k / a[i]; b[i] = a[i], b[i + n] = a[i + n]; } sort(b + 1, b + 2 * n + 1); int m = unique(b + 1, b + 2 * n + 1) - b; for (int i = 1; i <= 2 * n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b; for (int i = 0; i<n - 1; i++) { scanf("%d%d", &u, &v); g[u].push_back(v); vis[v]++; } int s; for (int i = 1; i <= n; i++) if (vis[i] == 0) { s = i; break; } dfs(s); printf("%lld\n", ans); } return 0; }