Weak Pair HDU - 5877（dfs+树状数组+离散化+二分）-白红宇

Weak Pair HDU - 5877（dfs+树状数组+离散化+二分）

阅读量：4136 次

发布时间：2019-05-25

本文共 1777 字，大约阅读时间需要 5 分钟。

You are given a rooted tree of N nodes, labeled from 1 to N. To the ith node a non-negative value ai is 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

2 3

1 2

Sample Output

给你一个树，去统计弱点对（两个点的权值积小于k），问有多少个这样的弱点对。

跟上一篇博客一样，也是dfs+树状数组。但是1e18的数据量，用树状数组肯定不行，所以需要离散化一下。在二分的时候，我们二分到了一个位置，用树状数组去更新。跑完一遍子树的时候，我们就统计这个子树里有多少对，然后直到跑完这个树。

代码如下：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;const int maxx=1e5+100;int head[maxx*2];bool vis[maxx];ll a[maxx],b[maxx],c[maxx*2];struct edge{ int to; int next;}e[maxx*2];int n,tot,sign,size;ll k,ans;/*-------------事前准备---------------*/ void init(){ memset(head,-1,sizeof(head)); memset(c,0,sizeof(c)); memset(vis,0,sizeof(vis)); tot=0;}void add(int x,int y){ e[tot].to=y,e[tot].next=head[x],head[x]=tot++;}/*-------------树状数组----------------*/ int lowbit(int x){return x&-x;}void update(int x,ll add){ while(x

努力加油a啊，(^o)/~

转载地址：http://myxvi.baihongyu.com/

你可能感兴趣的文章