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++】
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define LL __int64
#define mx 100005
std::map<LL, int> mp;
LL data[mx], dMP[mx], opt, k;
int n; struct Edge{
int to, next;
}edge[mx];
int iE, head[mx], d[mx], tr[mx << ], fid;
void addEdge(int u, int v){
edge[iE].to = v; edge[iE].next = head[u]; head[u] = iE++;
} void cnt(int l, int r, int now){
if (r <= fid){ opt += tr[now]; return; }
int mid = l + r >> ;
if (fid <= mid) return cnt(l, mid, now << );
opt += tr[now << ]; return cnt(mid + , r, now << | );
}
void sub(int l, int r, int now){
--tr[now];
if (l == r) return;
int mid = l + r >> ;
if (fid <= mid) return sub(l, mid, now << );
return sub(mid + , r, now << | );
}
void add(int l, int r, int now){
++tr[now];
if (l == r) return;
int mid = l + r >> ;
if (fid <= mid) return add(l, mid, now << );
return add(mid + , r, now << | );
} void DFS(int now){
int u;
LL temp;
if (data[now] == || (temp = k / data[now]) >= dMP[n]) fid = n;
else fid = std::upper_bound(dMP + , dMP + + n, temp) - dMP - ;
if (fid) cnt(, n, );
fid = mp[data[now]]; add(, n, );
for (u = head[now]; ~u; u = edge[u].next) DFS(edge[u].to);
fid = mp[data[now]]; sub(, n, );
} int main(){
int t, i, u, v;
scanf("%d", &t);
while (t--){
mp.clear(); memset(tr, , sizeof(tr));
scanf("%d%I64d", &n, &k);
for (i = ; i <= n; ++i) scanf("%I64d", &data[i]);
memcpy(dMP, data, sizeof(data));
std::sort(dMP + , dMP + n + );
for (i = ; i <= n; ++i) mp[dMP[i]] = i; memset(head, -, sizeof(head)); memset(d, , sizeof(d));
iE = ;
for (i = ; i < n; ++i){
scanf("%d%d", &u, &v);
addEdge(u, v); ++d[v];
} for (i = ; d[i]; ++i);
opt = ; DFS(i);
printf("%I64d\n", opt);
}
return ;
}