本文主要是介绍hdu 5877 - Weak Pair (2016大连网络赛) 离散化 + 树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出一棵树，n个节点，每个节点有一个权值，输入一个k，问有多少对点，满足点的权值乘积小于等于k，并且其中一个点是另一个点的祖先节点。
对于每一个节点，如果这个节点的权值为a，那么找到子节点所有的权值小于等于k/a的节点数量就是满足条件的对数（a=0时就是所有子节点都满足条件）。通过树状数组对统计做一个时间优化，用dfs处理，当处理到一个节点的时候，先减去树状数组中已经有的满足条件的数量，然后然后再将所有的子孙节点统计一遍，然后加上现在满足条件的节点数量。由于输入权值很大，所以要先进行离散化，将1e9范围的数字映射到1e5范围内。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
const int MAXN = 100010;
map<long long, int> s;
map<long long, int>::iterator p;
vector<int> ch[MAXN];
int c[MAXN * 2], id[MAXN];
int mx;
long long k, ans;
void add(int u) {while(u <= mx) {c[u]++;u += u & -u;}
}
int sum(int u) {int s = 0;while(u) {s += c[u];u -= u & -u;}return s;
}
void dfs(int u) {if(id[u])ans -= sum(s[k / id[u]]);else ans -= sum(mx);for(int i = 0; i < ch[u].size(); i++)dfs(ch[u][i]);if(id[u])ans += sum(s[k / id[u]]);else ans += sum(mx);add(s[id[u]]);
}
int main() {int t, i, j, n;scanf("%d", &t);while(t--) {scanf("%d%I64d", &n, &k);for(i = 1; i <= n; i++) {ch[i].clear();}s.clear();memset(c, 0, sizeof(c));for(i = 1; i <= n; i++) {scanf("%d", &id[i]);s[id[i]] = 0;if(id[i])s[k / id[i]] = 0;}mx = 0;for(p = s.begin(); p != s.end(); p++) {p->second = ++mx;}int u, v, h;for(i = 1; i < n; i++) {scanf("%d%d", &u, &v);ch[u].push_back(v);c[v] = 1;}for(h = 1; ; h++) {if(!c[h])break;}memset(c, 0, sizeof(c));ans = 0;dfs(h);printf("%I64d\n", ans);}return 0;
}
这篇关于hdu 5877 - Weak Pair (2016大连网络赛) 离散化 + 树状数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
