hdu 5877(树状数组+dfs)

时间：2021-11-29 09:22:56

Weak Pair

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2387    Accepted Submission(s): 740

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
 
Source
 
满足第一个条件的话进行DFS，然后统计父亲节点里面满足 val <= k/a[u] 的个数.这里可以用 树状数组进行维护.
///pro do this : a[l]%a[l+1]%...%a[r]

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <queue>

#include <string.h>

#include <vector>

using namespace std;

typedef long long LL;

const int N = ;

const LL INF = 1e19;

LL a[N],b[N],c[N];

int cnt,n,m;

int indegree[N];

struct Edge{

    int v,next;

}edge[N];

int head[N],tot;

LL ans,k;

void addEdge(int u,int v,int &k){

    edge[k].v = v,edge[k].next = head[u],head[u] = k++;

}

void init(){

    tot = ,ans = ;

    memset(head,-,sizeof(head));

    memset(indegree,,sizeof(indegree));

    memset(c,,sizeof(c));

}

int lowbit(int x){

    return x&(-x);

}

void update(int v,int idx){

    for(int i=idx;i<=cnt;i+=lowbit(i)){

        c[i] += v;

    }

}

LL getsum(int idx){

    LL ans=;

    for(int i=idx;i>=;i-=lowbit(i)){

        ans+=c[i];

    }

    return ans;

}

void dfs(int u){

    int x = upper_bound(b+,b+cnt+,k/a[u])-b-; ///upper_bound 第一个大于当前元素的第一个数的下标.

    int pos = lower_bound(b+,b+cnt+,a[u])-b; ///寻找离散化之后的下标

    ans+=getsum(x);

    update(,pos);

    for(int i=head[u];i!=-;i=edge[i].next){

        dfs(edge[i].v);

    }

    update(-,pos);

}

int main(){

    int tcase;

    scanf("%d",&tcase);

    while(tcase--){

        init();

        scanf("%d%lld",&n,&k);

        m = ;

        for(int i=;i<=n;i++){

            scanf("%lld",&a[i]);

            b[++m] = a[i];

            if(a[i]==) b[++m] = INF;

            else b[++m] = k/a[i];

        }

        sort(b+,b+m+);

        cnt = unique(b+,b+m+)-(b+);

        for(int i=;i<n;i++){

            int u,v;

            scanf("%d%d",&u,&v);

            addEdge(u,v,tot);

            indegree[v]++;

        }

        for(int i=;i<=n;i++){

            if(indegree[i]==) dfs(i);

        }

        printf("%lld\n",ans);

    }

    return ;

}

相关文章