題目鏈接

http://acm.split.hdu.edu.cn/showproblem.php?pid=5877

?

Problem 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? 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 Output For each test case, print a single integer on a single line denoting the number of weak pairs in the tree. Sample Input 1 2 3 1 2 1 2 Sample Output 1 題意：輸入n，k ?表示有n個(gè)節(jié)點(diǎn)的一棵樹，然后輸入n個(gè)節(jié)點(diǎn)的權(quán)值和n-1條邊，求點(diǎn)對(duì)（u，v）的對(duì)數(shù)，滿足： 1、u是v的祖先節(jié)點(diǎn)。 2、a[u]*a[v]<=k，a[]是存儲(chǔ)權(quán)值的數(shù)組。 思路：從根節(jié)點(diǎn)開始向下深搜，每到一個(gè)點(diǎn)時(shí)計(jì)算sum+=Sum（a[i]）,Sum(x)表示大于等于x的個(gè)數(shù)，然后向樹狀數(shù)組中加入k/a[i]，繼續(xù)遞歸深搜，退棧時(shí)從樹狀數(shù)組中減去k/a[i] ,這樣可以保證樹狀數(shù)組中存的一直是一條到根節(jié)點(diǎn)的路徑值。大題思路如上，這里要做一個(gè)離散化的處理，輸入的權(quán)值<=1e9 ?k<=1e18 ?而只有1e5個(gè)點(diǎn)，所以可以離散到2*1e5 后處理； 題解中提示用treap計(jì)算大于等于x的個(gè)數(shù)，這樣可以不需要進(jìn)行離散化； 第一次自己做出深搜的題，挺高興的^_^ ?看樣子我對(duì)深搜有了一點(diǎn)認(rèn)識(shí)了 代碼如下： #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <map> using namespace std; const long long maxn=200003; long long root; long long sum,k; long long in[100005]; vector<long long>g[100005]; long long a[100005]; long long b[200005];long long c[200005]; map<long long,long long>q;long long Lowbit(long long t) {return t&(t^(t-1)); } void add(long long x,long long t) {while(x > 0){c[x]+=t;x -= Lowbit(x);} } long long Sum(long long li) {long long s=0;while(li<200005){s+=c[li];li=li+Lowbit(li);}return s; }void dfs(long long t) {long long n=g[t].size();for(long long i=0;i<n;i++){long long v=g[t][i];sum+=(long long)Sum(q[a[v]]);if(a[v]==0) add(maxn,1);else add(q[k/a[v]],1);dfs(v);if(a[v]==0) add(maxn,-1);else add(q[k/a[v]],-1);} }int main() {long long T,N;scanf("%lld",&T);while(T--){q.clear();memset(in,0,sizeof(in));memset(c,0,sizeof(c));memset(b,0,sizeof(b));scanf("%lld%lld",&N,&k);for(long long i=1;i<=N;i++){scanf("%lld",&a[i]);b[2*i-2]=a[i];if(a[i]!=0)b[2*i-1]=k/a[i];g[i].clear();}sort(b,b+2*N);long long tot=0,pre=-1;for(long long i=0;i<2*N;i++){if(b[i]!=pre){pre=b[i];q[pre]=++tot;}}for(long long i=0;i<N-1;i++){long long aa,bb;scanf("%lld%lld",&aa,&bb);g[aa].push_back(bb);in[bb]++;}for(long long i=1;i<=N;i++)if(in[i]==0) { root=i; break; }sum=0;if(a[root]==0) add(maxn,1);else add(q[k/a[root]],1);dfs(root);printf("%lld\n",sum);}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/chen9510/p/5860058.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的2016 大连网赛---Weak Pair(dfs+树状数组)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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