題意

• 給我們一顆有根有向樹 以及每個點得權(quán)值a[1]~a[n] 需要我們求出在這顆樹種有多少對滿足以下兩個條件的pair
  （1）u是v的祖先節(jié)點 （2）a[u]*a[v]<= k
  N<=1e5
  a[i]<=1e9
  k<=1e18

分析

• 由于需要在樹中找符合要求的對數(shù) 一般的算法恐怕比較慢 考慮條件等式 如果我們把等式化簡一下 可以得到a[u]<= k/a[v] 也就是說
  我們對于每個點 我們可以從樹中向上找祖先節(jié)點所有小于等于k/a[v]值的點的個數(shù) 也就是能和當(dāng)前v點組成符合條件的對數(shù)
  關(guān)鍵是如何快速的求得我的祖先節(jié)點有多少個符合條件的個數(shù)呢？ 如果建樹后從當(dāng)前點向上遞歸 或是從根節(jié)點向下遞歸 向上遞歸每個節(jié)點
  都需要走所有的父親節(jié)點 最終的復(fù)雜度接近O(n^2) 從根節(jié)點向下遞歸 需要記錄每個節(jié)點的值 不好實現(xiàn)
  考慮如果我們把值元素插入到樹狀數(shù)組中 那么也就是說 每次對于當(dāng)前節(jié)點我們只需要到 樹狀數(shù)組中查找有多少個點 滿足不能是要求不就行了嗎
  復(fù)雜度O(n*logn)
  那么如何保證查到的都是祖先節(jié)點呢 我們就需要從根節(jié)點開始dfs查找 每次對于一個新節(jié)點 我們查找符合條件的點 查完后把當(dāng)前點插入進去 每次dfs回溯回來的時候就把該點的標(biāo)記刪除掉 以防影響其他搜索枝的查找
  為何采用DFS這樣就能保證每次查找一個節(jié)點 所有的祖先節(jié)點以及查找插入過了
  那么關(guān)于1e9我們可以離散化為每次輸入的節(jié)點數(shù)量1e5
  為了使不等式大小關(guān)系不變 我們需要把每個節(jié)點的值和k/權(quán)值 也算作輸入數(shù)據(jù)的一部分
  因為只有這樣 才能保證相對大小不變 離散化后 仍然符合原來數(shù)值的大小關(guān)系

離散化：

void Discret(){sort(li+1,li+1+(n<<1));//對數(shù)組中每個元素的大小排名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 前提是有序數(shù)組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了好幾十發(fā) 發(fā)現(xiàn)最后跳出循環(huán)的括號沒加WTF。。。寫代碼時還是最好不要擠在一行寫 容易眼缺。。。

總結(jié)

以上是生活随笔為你收集整理的Weak Pair HDU - 5877 树状数组+离散化+DFS遍历的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。