Weak Pair HDU - 5877 树状数组+离散化+DFS遍历

题意

• 给我们一颗有根有向树 以及每个点得权值a[1]~a[n] 需要我们求出在这颗树种有多少对满足以下两个条件的pair
  （1）u是v的祖先节点 （2）a[u]*a[v]<= k
  N<=1e5
  a[i]<=1e9
  k<=1e18

分析

• 由于需要在树中找符合要求的对数 一般的算法恐怕比较慢 考虑条件等式 如果我们把等式化简一下 可以得到a[u]<= k/a[v] 也就是说
  我们对于每个点 我们可以从树中向上找祖先节点所有小于等于k/a[v]值的点的个数 也就是能和当前v点组成符合条件的对数
  关键是如何快速的求得我的祖先节点有多少个符合条件的个数呢？ 如果建树后从当前点向上递归 或是从根节点向下递归 向上递归每个节点
  都需要走所有的父亲节点 最终的复杂度接近O(n^2) 从根节点向下递归 需要记录每个节点的值 不好实现
  考虑如果我们把值元素插入到树状数组中 那么也就是说 每次对于当前节点我们只需要到 树状数组中查找有多少个点 满足不能是要求不就行了吗
  复杂度O(n*logn)
  那么如何保证查到的都是祖先节点呢 我们就需要从根节点开始dfs查找 每次对于一个新节点 我们查找符合条件的点 查完后把当前点插入进去 每次dfs回溯回来的时候就把该点的标记删除掉 以防影响其他搜索枝的查找
  为何采用DFS这样就能保证每次查找一个节点 所有的祖先节点以及查找插入过了
  那么关于1e9我们可以离散化为每次输入的节点数量1e5
  为了使不等式大小关系不变 我们需要把每个节点的值和k/权值 也算作输入数据的一部分
  因为只有这样 才能保证相对大小不变 离散化后 仍然符合原来数值的大小关系

离散化：

void Discret(){sort(li+1,li+1+(n<<1));//对数组中每个元素的大小排名siz = unique(li+1,li+1+(n<<1))-li;//去重步骤 rep(i,1,n<<1)a[i] = lower_bound(li+1,li+1+siz,a[i])-li;// 查找排序去重后 原来的元素大小的位置赋值给原来的元素才能正确离散化 }

code

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <vector>using namespace std; typedef long long ll; const int N = 1e5+10;ll a[N<<1],li[N<<1],k,ans; int tre[N<<1],n; int bok[N]; vector<int>e[N];void Discret(){for(int i=1;i<=n*2;i++)li[i] = a[i];sort(li+1,li+1+n*2);int siz = unique(li+1,li+1+n*2)-li-1;// unique 前提是有序数组for(int i=1;i<=n*2;i++)a[i] = lower_bound(li+1,li+1+siz,a[i])-li;// 只有查找排序去重后 拿原来的元素找位置才能正确离散化 } int sum(int x){int s=0;while(x>0){s+=tre[x];x-=x&(-x);}return s; } void add(int x,int val) {while(x<=n*2){tre[x]+=val;x+=x&(-x);} } void dfs(int rt) {ans+=sum(a[rt+n]);add(a[rt],1);for(int i=0;i<e[rt].size();i++)dfs(e[rt][i]);add(a[rt],-1); } int main() {int t;scanf("%d",&t);while(t--){ans=0;memset(tre,0,sizeof(tre));memset(bok,0,sizeof(bok));scanf("%d%lld",&n,&k);for(int i=1;i<=n;i++)e[i].clear();for(int (i)=1;(i)<=n;(i)++){scanf("%lld",&a[i]);if(a[i]==0)a[i+n]=1e18;else a[i+n]= k/a[i];}Discret();for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);e[u].push_back(v);bok[v]++;}for(int i=1;i<=n;(i)++){if(!bok[i]){dfs(i);break;}}// 就是这忘记加括号了printf("%lld\n",ans);}return 0; }

WA了好几十发 发现最后跳出循环的括号没加WTF。。。写代码时还是最好不要挤在一行写 容易眼缺。。。

总结

以上是生活随笔为你收集整理的Weak Pair HDU - 5877 树状数组+离散化+DFS遍历的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。