HDU 5877 ：http://acm.hdu.edu.cn/showproblem.php?pid=5877
题意 ： 给N个点构成一颗树，再给一个K 。 寻找有几对 “虚弱的点对” 。 点对要求是，祖先节点 乘以 孩子节点的值小于等于K ，则这个祖先孩子点对为虚弱点对。。
啊，说实话，我是一点都没看出来这题和树状数组（区间求和）有个鬼联系。。。。 不看网上的题解，我表示想不出。。。
很可惜的是，即使我看了网上的题解，我也没有理解他们的思维所在。。。硬是墨墨叽叽啃了半天 DFS的代码，才稍微看懂了 如何用树状数组去联系这道题。。。
据说是大连区域赛网赛的最后一题。。。
还有两点，其一是，自己依然没有将离散化使用的融会贯通。比起直接使用map，我更倾向于自己写循环映射，但是不方便，多数情况下还是用map来进行离散操作来的方便；然而，刚刚发现离散化还有模板的，更加高贵优雅了。。。
其二是细节，此题的给出的数字的可以为0的情况，要细细思考（也许不用，仅仅是我太蠢），交了好多发总是WA。敲了2年多了代码，总是还有这个字母那个数组大小这个变量名混了的低级错误，导致自己找BUG找一百年啊一百年。。。水平还是需要提升的，不能太浮躁。
接下来讲一下此题的思路。大佬们做题目都是脑旁一个灯泡一亮，就悟道了；于是我这种咸鱼，看别人的博客，感受着别人“呐，就是这样就好了就A掉了”的情绪之时，我不但没看懂他们的代码思路，一脸懵逼之余，道心受到了巨大的创伤。。。。现在我讲题解，一定要讲的尽量健康快乐。。。。/(ㄒoㄒ)/~~
思路： 我们用数组A来保存每一个节点的值。
此题要求的“虚弱的点对”数，所需要满足的条件 必须要是 祖先 和 孩子 之间。 判断条件是否成立，也就是判断 “ A祖先 * A孩子 <= K ” 是否成立。
我们对这个条件移项，就可以得到 “ A祖先 <= K/(A孩子) ” 或者是 “ A孩子 <= K/(A祖先) ”
根据这个移项以后的等式，我们可以将问题转化为 ，
枚举每一个节点v ，我们要找出 小于等于 “ K/Av][” ，也就是小于等于这个商 的所有祖先节点的个数。 然后累加在一起。
等价的是 枚举每一个节点v ，我们要找出 小于等于 “ K/A[v]” ，也就是小于等于这个商 的所有孩子节点的个数。 然后累加在一起。
如果我们针对每个节点，来枚举孩子的话，会相对有些麻烦；因为每个节点的孩子，我们都要重新搜一遍才晓得； 如果我们针对每一个节点，来枚举他们的祖先节点，就会相对方便一些， 这是由于我们从根节点开始往下DFS的过程中，按照DFS的基本特性，是顺着一条树链向下搜的，结合回溯法以后，我们便可以实现“边DFS，边计算”的思想。
那么，树状数组在这里怎么体现的呢？ ——对于一个点v，如何查找 满足条件的祖先节点的个数是多少个呢？ 标记作用的树状数组经典实用方法。
满足条件 ——也就是 祖先点值 <= K/ A[V] 。 我们将所有节点的值A[i]以及每个节点对应的商 ，都放入到树状数组中。那么我们可以在DFS过程中，每搜过一个节点，就将此节点的值 在树状数组中标记为1，含义为“此点出现过了”。（add操作）而统计祖先节点的过程， 就是 在树状数组中 ，将小于等 当前节点 的商 的所有值的标记累加，进行树状数组的求和操作。（cal_sum操作） 在一条树链的DFS搜索结束以后，还要回溯，消除掉这个标记，因为对别的树链而言，这条树链就不是它那条树链的祖先了，就是使用add操作加上-1即可。
离散化操作。错了很多遍，很多问题都是出现在离散化上面。
为什么要离散，因为树状数组的大小太大是会爆的。我们只能开500000的大小，而A[i]的范围却是999999999，所以要把这些A[i]离散掉利于解题。
注意的是：这道题是 不仅仅要离散所有A[i]，还要离散 K/A[i] ，并且是同时离散，离散在一个数组里面。 为的是实现 add(A[i]) ，而 cal_sum( K/A[i] )。 所以树状数组的大小是2*n 而不是n 。要注意越界问题。
A[i] 可以等于0 的细节问题。
当A[i}等于0的时候，是没办法计算K/A[i] 的，会出现错误，所以要注意一下。那如何处置呢。我们前面讨论过，点值是为了更新，商值是为了求和。而但A[i]等于0的时候，其所有子节点都是满足条件的。所以我们不能将其离散为-1（为什么是-1，因为我就是-1然后WA了。。），应当映射为无穷大（取9个9就行了哈）。
这是我找了万年BUG以后终于A掉的代码，但是后面我会放上经过我的修改以及排版之后，别的大佬的代码，他们的思路更加清晰直观，最好看我的博客思路，代码还是看第二种的好一些~~
我的垃圾代码： 用map来离散。这里的pos数组在DFS中没什么用，因为是为了用来方便map离散的。
#include"bits/stdc++.h" using namespace std; #define inf 100009 #define INF 999999999 #define loop(x,y,z) for(x=y;x<z;x++) #define ll long long int n; //点数 ll k; //积值 vector<int>edge[inf]; //边 int node[inf]; //点值 ll pos[inf*2]; //每个点的 k/node[i] map<ll,int>m; int c[2*inf]; //树状数组 ll ans; //最终结果 int book[inf]; //标记数组，为了找出根节点 void init() { int i; loop(i,1,n+1)edge[i].clear(); m.clear(); memset(c,0,sizeof c); memset(book,0,sizeof book); ans=0; } int lowbit(int i) { return i&-i; } int cal_sum(int i) { int sum=0; while(i>0) { sum+=c[i]; i-=lowbit(i); } return sum; } void add(int i,int t) { while(i<=2*n) { c[i]+=t; i+=lowbit(i); } } void dfs(int u) { ll t=node[u]?m[k/node[u]]:2*inf-10; //这个值所对应的映射 ans+=cal_sum(t); int len=edge[u].size(),i;//printf("%d\n",m[pos[u]]); add(m[node[u]],1); loop(i,0,len) { int v=edge[u][i]; dfs(v); } add(m[node[u]],-1); } int main() { int i,j,T,root; scanf("%d",&T); while(T--) { init(); scanf("%d%lld",&n,&k); loop(i,1,n+1) { scanf("%d",&node[i]); //存放每个点的值 if(node[i]) pos[i]=k/node[i]; //每个点的k/node[i] else pos[i]=-1; pos[i+n]=node[i]; } //开始映射 sort(pos+1,pos+1+n+n); j=0; loop(i,1,2*n+1) { if(pos[i]!=pos[i-1])j++; m[pos[i]]=j; } loop(i,1,n) { int u,v; scanf("%d%d",&u,&v); edge[u].push_back(v); book[v]=1; } loop(i,1,n+1)if(!book[i]){root=i;break;} //找根 dfs(root); printf("%lld\n",ans); } return 0; }
另一种高级代码： 用模板来离散，离散以后的离散表就是pos数组，pos数组的前n个为节点值的离散，后n个为 商值 的离散哦。所以DFS那边一会是 u+n 一会是 u，要理解。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <vector> #define ll __int64 using namespace std; #define inf 100009 #define INF 999999999 #define loop(x,y,z) for(x=y;x<z;x++) #define ll long long int book[inf]; //book[i]为0的为root int c[inf*2],n; vector<int>edge[inf]; ll k,ans; ll pos[inf*2],li[inf*2]; void init() { //m.clear(); int i; loop(i,1,n+1)edge[i].clear(); memset(c,0,sizeof c); memset(book,0,sizeof book); ans=0; } int lowbit(int i) { return i&-i; } int cal_sum(int i) { int sum=0; while(i>0){ sum+=c[i]; i-=lowbit(i); } return sum; } void add(int i,int t) { while(i<=2*n){ c[i]+=t; i+=lowbit(i); } } void dfs(int u){ ans+=cal_sum(pos[u+n]);//在它之前进入的都为它的祖先 add(pos[u], 1); for(int i=0; i<edge[u].size(); i++){ int v=edge[u][i]; dfs(v); } add(pos[u], -1);//该节点的子树全都遍历完了 该节点不是任何节点的祖先时 删除该节点的值 } void lisan(ll x[]){//离散化模板 for(int i=1; i<=2*n; i++)li[i]=x[i]; sort(li+1, li+2*n+1);//unique的作用是“去掉”容器中相邻元素的重复元素,它实质上是一个伪去除， int m=unique(li+1, li+2*n+1)-li-1;//它会把重复的元素添加到容器末尾，而返回值是去重之后的尾地址 for(int i=1; i<=2*n; i++)x[i]=lower_bound(li+1, li+m+1, x[i])-li;//一般使用前需要对容器进行排序 }//m也等于去重数组的大小 int main() { int i,j,T,root; scanf("%d",&T); while(T--) { init(); scanf("%d%lld",&n,&k); loop(i,1,n+1) { scanf("%lld",&pos[i]); if(pos[i]==0)pos[i+n]=inf; else pos[i+n]=k/pos[i]; } lisan(pos);//数据a[i]<=10^9 n<=10^5 数据离散化使a[i]的范围中10^5内 //使得树状数组的空间不溢出 loop(i,1,n) { int u,v; scanf("%d%d",&u,&v); edge[u].push_back(v); book[v]=1; } loop(i,1,n+1)if(!book[i]){root=i;break;} //找根 dfs(root); printf("%lld\n",ans); } return 0; }
