HDU5877 Weak Pair

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 #define REP(i,n)                for(int i(0); i <  (n); ++i)
  6 #define rep(i,a,b)              for(int i(a); i <= (b); ++i)
  7 #define dec(i,a,b)              for(int i(a); i >= (b); --i)
  8 #define for_edge(i,x)           for(int i = H[x]; i; i = X[i])
  9 
 10 #define LL      long long
 11 #define ULL     unsigned long long
 12 #define MP      make_pair
 13 #define PB      push_back
 14 #define FI      first
 15 #define SE      second
 16 #define INF     1 << 30
 17 
 18 const int N     =    300000      +       10;
 19 const int M     =    10000       +       10;
 20 const int Q     =    1000        +       10;
 21 const int A     =    30          +       1;
 22 
 23 
 24 struct Node{
 25     LL num;
 26     int id;
 27     friend bool operator < (const Node &a, const Node &b){
 28         return a.num < b.num;
 29     }
 30 } tree[N];
 31 
 32 int E[N << 1], X[N << 1], H[N << 1];
 33 LL a[N];
 34 int T, et;
 35 int n;
 36 LL k;
 37 int x, y;
 38 LL rk[N], f[N];
 39 LL now;
 40 int l, r;
 41 bool pa[N];
 42 int root;
 43 LL c[N];
 44 LL ans;
 45 bool v[N];
 46 
 47 inline void addedge(int a, int b){
 48     E[++et] = b, X[et] = H[a], H[a] = et;
 49 }
 50 
 51 inline void add(LL x, LL val){ 
 52     for (; x <= n; x += (x) & (-x)) 
 53         c[x] += val;
 54 }
 55 
 56 inline LL query(LL x){
 57     LL ret(0); 
 58     for (; x; x -= (x) & (-x)) ret += c[x]; 
 59     return ret;
 60 }
 61 
 62 void dfs(int x){
 63     add(rk[x], 1);
 64     for_edge(i, x) if (!v[E[i]]) dfs(E[i]), v[E[i]] = true;
 65     add(rk[x], -1);
 66     ans += query(f[x]);
 67 }
 68 
 69 
 70 int main(){
 71 
 72     scanf("%d", &T);
 73     while (T--){
 74         et = 0;
 75         scanf("%d%lld", &n, &k);
 76         rep(i, 1, n) scanf("%lld", a + i);
 77         memset(v, false, sizeof v);
 78         memset(pa, true, sizeof pa);
 79         memset(tree, 0, sizeof tree);
 80         memset(H, 0, sizeof H);
 81         rep(i, 1, n - 1){
 82             scanf("%d%d", &x, &y);
 83             addedge(x, y);
 84             pa[y] = false;
 85         }
 86 
 87         rep(i, 1, n){
 88             tree[i].num = a[i];
 89             tree[i].id = i;
 90         }
 91 
 92         sort(tree + 1, tree + n + 1);
 93         rk[tree[1].id] = 1;
 94         rep(i, 2, n) 
 95             if (tree[i].num == tree[i - 1].num) rk[tree[i].id] = rk[tree[i - 1].id];
 96             else rk[tree[i].id] = rk[tree[i - 1].id] + 1;
 97 
 98         rep(i, 1, n){
 99             now = k / a[i];
100             l = 1; r = n;
101             if (tree[1].num > now) f[i] = 0; 
102             else{    
103                 while (l + 1 < r){
104                     int mid = (l + r) >> 1;
105                     if (tree[mid].num <= now) l = mid;
106                     else r = mid - 1;
107                 }
108 
109                 if (tree[r].num <= now) l = r;
110                 f[i] = rk[tree[l].id];
111             }
112 
113         }
114         root = 0;
115         rep(i, 1, n) if (pa[i]){ root = i; break;}
116         memset(c, 0, sizeof c);
117         ans = 0;
118         v[root] = true;
119         dfs(root);
120         printf("%lld\n", ans);
121 
122 
123     }
124 
125 
126 
127     return 0;
128 
129 }