1. 首页
2. DFS, 线段树
3. 本页

HDU 5877 Weak Pair (线段树+离散化+DFS)

题目链接：点我~~

题意：给出一棵n个结点的树和一个数$k$, 每个节点上有权值ai, 问有多少个有序对(u,v)满足$u$是$v$的祖先, 且au*av≤k.

思路：从根开始dfs, 用线段树维护当前节点$u$到根的节点权值序列, 数据很大,需要离散化,然后就查询小于等于k/au的数的个数. 之后把au插入, 然后继续查找子节点,回溯的时候再删去该节点。其实就是查找每个节点有多少个父节点满足条件，就是一遍dfs的过程。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN = 100100;

LL tree[MAXN<<3];
LL val[MAXN*2],a[MAXN];
int dep[MAXN],cnt;
LL ans,k;

struct node
{
    int v,u,next;
} edge[MAXN*2];
int head[MAXN*2];
int tol;
void init()
{
    memset(head,-1,sizeof(head));
    tol=0;
}

void addedge(int u,int v)
{
    edge[tol].v=v;
    edge[tol].next=head[u];
    head[u]=tol++;
}

inline PushUp(int rt)
{
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}

void build(int l,int r,int rt)
{
    if(l==r)
    {
        tree[rt]=0;
        return;
    }
    LL m=(l+r)>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}

void modify(int pos,int add,int l,int r,int rt)
{
    if(l==r)
    {
        tree[rt]+=add;
        return;
    }
    int m=(l+r)>>1;
    if(pos<=m)
        modify(pos,add,lson);
    else
        modify(pos,add,rson);
    PushUp(rt);
}

int query(int L,int R,int l,int r,int rt)
{
    if(L<=l && r<=R)
    {
        return tree[rt];
    }
    int res=0;
    int m=(l+r)>>1;
    if(L<=m)
        res+=query(L,R,lson);
    if(R>m)
        res+=query(L,R,rson);
    return res;
}

void dfs(int u,int fa)
{
    int pos=lower_bound(val,val+cnt,k/a[u])-val;
    ans+=query(0,pos,0,cnt,1);
    pos=lower_bound(val,val+cnt,a[u])-val;
    modify(pos,1,0,cnt,1);
    for(int i=head[u]; ~i; i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==fa)
            continue;
        dfs(v,u);
    }
    modify(pos,-1,0,cnt,1);
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        init();
        scanf("%d%lld",&n,&k);
        cnt=0;
        for(int i=1; i<=n; ++i)
        {
            scanf("%lld",&a[i]);
            val[cnt++]=a[i];
        }
        for(int i=1; i<=n; ++i)
        {
            val[cnt++]=k/a[i];
        }
        sort(val,val+cnt);
        cnt=unique(val,val+cnt)-val;
        int u,v;
        memset(dep,0,sizeof(dep));
        for(int i=0; i<n-1; ++i)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
            dep[v]++;
        }
        build(0,cnt,1);
        int root;
        for(int i=1; i<=n; ++i)
        {
            if(dep[i]==0)
            {
                root=i;
                break;
            }
        }
        ans=0;
        dfs(root,0);
        printf("%lld\n",ans);
    }
    return 0;
}