HDU 5877-Weak Pair(主席树 dfs序)

HDU 5877-Weak Pair

相当于子树中有多少个点满足,dfs序列之后就是区间查找了.

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
#define sc scanf
#define itn int
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;
using namespace std;
const int N=1e5+5;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=x*(a/b);}
int n,sz;
ll a[N],b[N],c[N],k;
int du[N]={0};
int L[N],R[N],cnt=0,tot=0;
vector<int>g[N];
int T[N*30],Losn[N*30],Rson[N*30],rtsum[N*30];
int getid(ll x){return lower_bound(b+1,b+1+sz,x)-b;};
void dfs(int u){
    L[u]=++cnt;
    c[cnt]=a[u];
    for(int v:g[u])dfs(v);
    R[u]=cnt;
};
int tree(int l,int r){
    int rt=++tot;
    rtsum[rt]=0;
    int mid=l+r>>1;
    if(l<r){
        Losn[rt]=tree(l,mid);
        Rson[rt]=tree(mid+1,r);
    };
    return rt;
};
int ins(int u,int l,int r,int pos){
    int rt=++tot;
    rtsum[rt]=rtsum[u]+1;
    Losn[rt]=Losn[u],Rson[rt]=Rson[u];
    int mid=l+r>>1;
    if(l<r){
        if(pos<=mid)Losn[rt]=ins(Losn[u],l,mid,pos);
        else Rson[rt]=ins(Rson[u],mid+1,r,pos);
    };
    return rt;
};
int Q(int v,int u,int l,int r,int pos){
    if(l>r)return 0;
    if(l>pos)return 0;
    if(r<=pos)return rtsum[u]-rtsum[v];
    int mid=l+r>>1;
    int sum=0;
    sum+=Q(Losn[v],Losn[u],l,mid,pos);
    sum+=Q(Rson[v],Rson[u],mid+1,r,pos);
    return sum;
};
int main(){
    int t;
    cin>>t;{
        while(t--){
            tot=cnt=0;
            sc("%d%lld",&n,&k);
            for(int i=1;i<=n;i++)sc("%lld",&a[i]),b[i]=a[i],g[i].clear(),du[i]=0;
            sort(b+1,b+1+n);
            sz=unique(b+1,b+1+n)-b-1;
            for(int i=1;i<n;i++){
                int u,v;
                sc("%d%d",&u,&v);
                du[v]++;
                g[u].push_back(v);
            };
            int root=1;
            for(int i=1;i<=n;i++)if(du[i]==0){root=i;break;};
            dfs(root);
            T[0]=tree(1,sz);
            for(int i=1;i<=n;i++)T[i]=ins(T[i-1],1,sz,getid(c[i]));
            ll ans=0;
            for(int i=1;i<=n;i++){
                if(a[i]==0){ans+=R[i]-L[i];continue;};
                if(L[i]==R[i])continue;
                int id=upper_bound(b+1,b+1+sz,k/a[i])-b-1;
                int x=Q(T[L[i]],T[R[i]],1,sz,id);
                ans+=x;
            };
            printf("%lld\n",ans);
        };
    };
};