題目鏈接：點擊查看

題目大意：給定一個n個節(jié)點的樹，每個節(jié)點都有權(quán)值，現(xiàn)在定義weak pair(u,v)需要滿足的兩個條件：

u是v的祖先；

;

問給定的樹中有多少個weak pair；

題目分析：我們可以將問題轉(zhuǎn)化一下，要求，可以兩邊同除，得到，即用dfs序從根節(jié)點跑一邊樹，記錄截止到任意子節(jié)點為止，之前有多少個小于等于的父節(jié)點即可，用樹狀數(shù)組或線段樹維護(hù)數(shù)量就行，這里偷個懶用樹狀數(shù)組維護(hù)的。上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;//記得將邊界擴(kuò)大為2倍int n;LL k;LL c[N];LL a[N];int in[N];//維護(hù)入度vector<LL>v;//離散化用vector<int>node[N];//鄰接表int lowbit(int x) {return x&(-x); }void update(int pos,int val) {while(pos<=2*n)//一定要注意，因為在離散化的過程中加入了k/a[u]這一個值，所以最后的上限擴(kuò)大為了2*n{c[pos]+=val;pos+=lowbit(pos);} }LL query(int pos) {LL ans=0;while(pos){ans+=c[pos];pos-=lowbit(pos);}return ans; }LL ans;void dfs(int u) {//這里二分注意一下，需要讓頂點右移一個單位，因為樹狀數(shù)組只能處理正整數(shù)int q=lower_bound(v.begin(),v.end(),a[u])-v.begin()+1;//記錄a[u]的編號int p=lower_bound(v.begin(),v.end(),k/a[u])-v.begin()+1;//記錄k/a[u]的編號ans+=query(p);//查找該子節(jié)點先前有多少個父節(jié)點在區(qū)間[1,k/a[u]]中update(q,1);//將該節(jié)點加入for(int i=0;i<node[u].size();i++)dfs(node[u][i]);update(q,-1);//訪問完該節(jié)點的子樹后記得將該節(jié)點移除 }int main() { // freopen("input.txt","r",stdin)int w;cin>>w;while(w--){v.clear();memset(c,0,sizeof(c));memset(in,0,sizeof(in));scanf("%d%lld",&n,&k);for(int i=1;i<=n;i++){node[i].clear();scanf("%lld",a+i);v.push_back(a[i]);v.push_back(k/a[i]);}for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);in[v]++;}int root;for(int i=1;i<=n;i++)if(!in[i]){root=i;break;}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());ans=0;dfs(root);printf("%lld\n",ans);}/*由于題目給的樣例數(shù)據(jù)太水，這里從別人那里找來一組數(shù)據(jù)：input:39 102 4 7 9 2 11 7 4 11 21 32 42 53 63 73 86 99 102 4 7 9 2 11 7 4 11 21 32 42 53 63 73 86 98 102 4 7 9 2 11 7 41 21 32 42 53 63 73 8output:664*/return 0; }

?

總結(jié)

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

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