hdu_5877_Weak Pair(离散+DFS+树状数组)

题意：

给你一棵树，让你找有多少对满足那两个条件的weak pair

题解：

有人用Treap,我不会，然后我用树状数组+离散来替代Treap，用DFS搜到叶子，然后在树状数组中找小于k/a[u]的个数，注意a[u]可以为0,要处理一下

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;i++)
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 const int N=1e5+7;
 7 int t,n,v[N],g[N],nxt[N],ed,sum[N],in[N],edn;
 8 ll k,a[N],hsh[N],ans;
 9 
10 inline int getid(ll x){return upper_bound(hsh+1,hsh+1+edn,x)-hsh-1;}
11 inline void add(int x,int c){while(x<=n)sum[x]+=c,x+=x&-x;}
12 inline int ask(int x){int an=0;while(x)an+=sum[x],x-=x&-x;return an;}
13 
14 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}
15 
16 void dfs(int u)
17 {
18     add(getid(a[u]),1);
19     for(int i=g[u];i;i=nxt[i])dfs(v[i]);
20     add(getid(a[u]),-1);
21     ll tp;
22     if(a[u]!=0)tp=k/a[u];else tp=hsh[edn]+1;
23     if(tp>hsh[edn])tp=hsh[edn]+1;
24     ans+=ask(getid(tp));
25 }
26 
27 int main()
28 {
29     scanf("%d",&t);
30     while(t--)
31     {
32         scanf("%d%lld",&n,&k);
33         F(i,1,n)scanf("%lld",a+i),hsh[i]=a[i];
34         sort(hsh+1,hsh+1+n),memset(sum,0,sizeof(sum));
35         memset(in,0,sizeof(in)),edn=1;
36         memset(g,0,sizeof(g)),ed=0,ans=0;
37         F(i,2,n)if(hsh[i]!=hsh[edn])hsh[++edn]=hsh[i];
38         F(i,1,n-1)
39         {
40             int x,y;
41             scanf("%d%d",&x,&y);
42             adg(x,y),in[y]++;
43         }
44         F(i,1,n)if(!in[i]){dfs(i);break;}
45         printf("%lld
",ans);
46     }
47     return 0;
48 }

View Code