Weak Pair
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 ord
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
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
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
题意：给你一颗树，给点的权值，和树的边，求每个点v的祖先u，并且a[u]*a[v]<=K；
思路：利用dfs序可以快速的得到每个点的祖先，每次更新a[u]，找到k/a[v]>=a[u]的个数树状数组优化；
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
const int N=1e5+10,M=4e6+10,inf=1e9+10,mod=1e9+7;
const ll INF=1e18+10;
vector<int>v[N];
int du[N];
ll l[N<<1],a[N];
int n,len;
ll k,ans;
int tree[N<<1];
void init(int n)
{
for(int i=1;i<=n;i++)
v[i].clear();
memset(tree,0,sizeof(tree));
memset(du,0,sizeof(du));
ans=0;
}
int getpos(ll x)
{
int pos=lower_bound(l,l+len,x)-l;
return pos+1;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int c)
{
while(x<(N<<1))
{
tree[x]+=c;
x+=lowbit(x);
}
}
ll query(int x)
{
ll ans=0;
while(x)
{
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
void dfs(int u)
{
int p,q;
if(a[u])
p=getpos(k/a[u]);
else
p=(N<<1)-1;
if(a[u])
q=getpos(a[u]);
else
q=1;
ans+=query(p);
update(q,1);
for(int i=0;i<v[u].size();i++)
{
dfs(v[u][i]);
}
update(q,-1);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int flag=0;
scanf("%d%lld",&n,&k);
init(n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]),l[flag++]=k/a[i],l[flag++]=a[i];
sort(l,l+flag);
len=unique(l,l+flag)-l;
for(int i=1;i<n;i++)
{
int u,w;
scanf("%d%d",&u,&w);
v[u].push_back(w);
du[w]++;
}
for(int i=1;i<=n;i++)
if(du[i]==0)
dfs(i);
printf("%lld
",ans);
}
return 0;
}