首页 > 代码库 > HDOJ5877(dfs序+离散化+树状数组)

HDOJ5877(dfs序+离散化+树状数组)

2024-08-13 10:39:18   221人阅读

Weak Pair

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


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 weakif
  (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
 
思路：将公式au*av<=k变换为 au<=k/av。 在遍历结点v的过程中，统计au<=k/av的节点u的个数。
#include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int MAXN=100005;int n;LL k;vector<int> arc[MAXN];LL val[MAXN];LL buf[MAXN+MAXN];int top;int deg[MAXN];int bit[MAXN+MAXN];void add(int i,int x){    int limit=MAXN+MAXN;    while(i<limit)    {        bit[i]+=x;        i+=(i&(-i));    }}int sum(int i){    int s=0;    while(i>0)    {        s+=bit[i];        i-=(i&(-i));    }    return s;}int vis[MAXN];LL res;void dfs(int u){    vis[u]=1;    int has1=lower_bound(buf,buf+top,k/val[u])-buf+1;    int s=sum(has1);    for(int i=0;i<arc[u].size();i++)    {        int to=arc[u][i];        if(!vis[to])        {            dfs(to);        }    }    res+=(sum(has1)-s);    int has2=lower_bound(buf,buf+top,val[u])-buf+1;    add(has2,1);} int main(){    int T;    scanf("%d",&T);    while(T--)    {        res=0;        memset(vis,0,sizeof(vis));        memset(bit,0,sizeof(bit));        top=0;        memset(deg,0,sizeof(deg));        scanf("%d%lld",&n,&k);        for(int i=1;i<=n;i++)        {            arc[i].clear();            scanf("%lld",&val[i]);        }        for(int i=0;i<n-1;i++)        {            int u,v;            scanf("%d%d",&u,&v);            arc[u].push_back(v);            arc[v].push_back(u);            deg[v]++;        }        for(int i=1;i<=n;i++)        {            buf[top++]=val[i];        }        for(int i=1;i<=n;i++)        {            buf[top++]=k/val[i];        }        sort(buf,buf+top);        for(int i=1;i<=n;i++)        {            if(deg[i]==0)            {                dfs(i);                break;            }        }        printf("%lld\n",res);    }    return 0;}

 

 

HDOJ5877(dfs序+离散化+树状数组)


联系
我们