首页 > 代码库 > HDU 5877 Weak Pair(弱点对)
HDU 5877 Weak Pair(弱点对)
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) au × av ≤ k.
Can you find the number of weak pairs in the tree? | 给你有N个节点的有根树,编号从1到N。第i个节点会被分配一个非负数ai。一个满足如下条件的有序点对(u, v)则被认为是弱点对 (1)u是v的先祖节点(注意:这个问题中u不能为自身的先祖节点)。 (2) au X av ≤ 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≤105
0≤ai≤109
0≤k≤1018 | 多组测试用例。 输入的第一行有一个整数T表示测试用例的数量。 对于每个测试用例,第一行有两个用空格分隔的整数,N与k, 第二行有N个用空格分隔的整数,表示a1到aN。 随后每(N-1)行有两个用空格分隔的数u与v表示连接两节点的一条边,其中u是v的父节点。
范围如下:
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 - 输入样例 | Sample Output - 输出样例 |
1 | 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\n", opt);72 }73 return 0;74 }
HDU 5877 Weak Pair(弱点对)