# HDU 5877 Weak Pair(离散化+dfs+树状数组)

2016-09-12

HDU 5877 Weak Pair(离散化+dfs+树状数组)

# HDU 5877 Weak Pair

Accept: 0 Submit: 0

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

## 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&times;av&le;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&le;N&le;10^5

0&le;ai&le;10^9

0&le;k&le;10^18

## Output

For each test case, print a single integer on a single line denoting the number of weak pairs in the tree.

1

2 3

1 2

1 2

1

【题意】

【类型】

【分析】

## Source Code

```/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100005;
const int M = 20005;
const __int64 inf = 1e18+1;
const int mod = 1000000007;
struct edge
{
int v,to;
}e[N];
int p,q,h[N],a[N],c[2*N];
bool vis[N];
__int64 k,s[2*N],ans;
void add_edge(int u,int v)
{
e[p].v=v;
e[p].to=h[u];
h[u]=p++;
}
int lowbit(int t)
{//计算c[t]展开的项数
return t&(-t);
}
void update(int i,int x)
{
while(i<=q)
{
c[i]=c[i]+x;
i+=lowbit(i);
}
}
int Sum(int n) //求前n项的和.
{
int sum=0;
while(n>0)
{
sum+=c[n];
n-=lowbit(n);
}
return sum;
}
void dfs(int x)
{
int i;
ans+=Sum(lower_bound(s,s+q,a[x]?k/a[x]:inf)-s+1);
update(lower_bound(s,s+q,a[x])-s+1,1);
for(i=h[x];i+1;i=e[i].to)
dfs(e[i].v);
update(lower_bound(s,s+q,a[x])-s+1,-1);
}
int main()
{
int t,n,i,u,v;
scanf("%d",&t);
while(t--)
{
p=q=0;
ans=0;
memset(h,-1,sizeof(h));
memset(c,0,sizeof(c));
memset(vis,false,sizeof(vis));
scanf("%d%I64d",&n,&k);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s[q++]=a[i];
if(!a[i])
s[q++]=inf;
else
s[q++]=k/a[i];
}
sort(s,s+q);
q=unique(s,s+q)-s;
for(i=1;i菜鸟成长记

```