HDU 5877 Weak Pair（弱点对）

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

Description

题目描述

You are given a rooted tree of N nodes, labeled from 1 to N. To the ith 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) a_u × a_v ≤ k.

Can you find the number of weak pairs in the tree?

给你有N个节点的有根树，编号从1到N。第i个节点会被分配一个非负数ai。一个满足如下条件的有序点对(u, v)则被认为是弱点对

(1)u是v的先祖节点(注意：这个问题中u不能为自身的先祖节点)。

(2) a_u X a_v ≤ k

你能找出这棵树里有多少弱点对吗？

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≤10⁵

0≤ai≤10⁹

0≤k≤10¹⁸

多组测试用例。

输入的第一行有一个整数T表示测试用例的数量。

对于每个测试用例，第一行有两个用空格分隔的整数，N与k，

第二行有N个用空格分隔的整数，表示a1到aN。

随后每(N-1)行有两个用空格分隔的数u与v表示连接两节点的一条边，其中u是v的父节点。

范围如下:

1≤N≤10⁵

0≤ai≤10⁹

0≤k≤10¹⁸

Output	输出
For each test case, print a single integer on a single line denoting the number of weak pairs in the tree.	对于每个测试用例，输出一个表示树中弱点对数量的整数在单独一行。

Sample Input - 输入样例	Sample Output - 输出样例
1 2 3 1 2 1 2	1

【题解】

DFS + 离散化线段树

用DFS从上往下（从根往叶子）添加与释放节点进线段树，利用线段树查找符合的区间中元素数量。

因为单个数的值比较大，但是总数比较少，线段树还算可以接受。根据总数进行离散化，其实就是排个序+map。出于想用upper_bound的强迫症没有把k/ai的结果一并加入离散化（注意0），不然代码量应该更少。

【代码 C++】

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <map>
 5 #define LL __int64
 6 #define mx 100005
 7 std::map<LL, int> mp;
 8 LL data[mx], dMP[mx], opt, k;
 9 int n;
10 
11 struct Edge{
12     int to, next;
13 }edge[mx];
14 int iE, head[mx], d[mx], tr[mx << 2], fid;
15 void addEdge(int u, int v){
16     edge[iE].to = v; edge[iE].next = head[u]; head[u] = iE++;
17 }
18 
19 void cnt(int l, int r, int now){
20     if (r <= fid){ opt += tr[now]; return; }
21     int mid = l + r >> 1;
22     if (fid <= mid) return cnt(l, mid, now << 1);
23     opt += tr[now << 1]; return cnt(mid + 1, r, now << 1 | 1);
24 }
25 void sub(int l, int r, int now){
26     --tr[now];
27     if (l == r) return;
28     int mid = l + r >> 1;
29     if (fid <= mid) return sub(l, mid, now << 1);
30     return sub(mid + 1, r, now << 1 | 1);
31 }
32 void add(int l, int r, int now){
33     ++tr[now];
34     if (l == r) return;
35     int mid = l + r >> 1;
36     if (fid <= mid) return add(l, mid, now << 1);
37     return add(mid + 1, r, now << 1 | 1);
38 }
39 
40 void DFS(int now){
41     int u;
42     LL temp;
43     if (data[now] == 0 || (temp = k / data[now]) >= dMP[n]) fid = n;
44     else fid = std::upper_bound(dMP + 1, dMP + 1 + n, temp) - dMP - 1;
45     if (fid) cnt(1, n, 1);
46     fid = mp[data[now]]; add(1, n, 1);
47     for (u = head[now]; ~u; u = edge[u].next) DFS(edge[u].to);
48     fid = mp[data[now]]; sub(1, n, 1);
49 }
50 
51 int main(){
52     int t, i, u, v;
53     scanf("%d", &t);
54     while (t--){
55         mp.clear(); memset(tr, 0, sizeof(tr));
56         scanf("%d%I64d", &n, &k);
57         for (i = 1; i <= n; ++i) scanf("%I64d", &data[i]);
58         memcpy(dMP, data, sizeof(data));
59         std::sort(dMP + 1, dMP + n + 1);
60         for (i = 1; i <= n; ++i) mp[dMP[i]] = i;
61 
62         memset(head, -1, sizeof(head)); memset(d, 0, sizeof(d));
63         iE = 0;
64         for (i = 1; i < n; ++i){
65             scanf("%d%d", &u, &v);
66             addEdge(u, v); ++d[v];
67         }
68 
69         for (i = 1; d[i]; ++i);
70         opt = 0; DFS(i);
71         printf("%I64d
", opt);
72     }
73     return 0;
74 }