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 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

分析：dfs+树状数组+离散化；

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <list>

#define rep(i,m,n) for(i=m;i<=n;i++)

#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)

#define mod 1000000007

#define inf 0x3f3f3f3f

#define vi vector<int>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define ll long long

#define pi acos(-1.0)

#define pii pair<int,int>

#define Lson L, mid, rt<<1

#define Rson mid+1, R, rt<<1|1

const int maxn=2e5+;

using namespace std;

ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}

ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}

int n,m,k,t,h[maxn],tot,q[maxn],fa[maxn],num;

ll ans,a[maxn],b[maxn],c[maxn];

struct node

{

    int to,nxt;

}e[maxn];

void add(int x,int y)

{

    tot++;

    e[tot].to=y;

    e[tot].nxt=h[x];

    h[x]=tot;

}

void gao(int x,int y)

{

    for(int i=x;i<=num+;i+=(i&(-i)))

        q[i]+=y;

}

int get(int x)

{

    int ret=;

    for(int i=x;i;i-=(i&(-i)))

        ret+=q[i];

    return ret;

}

void dfs(int now)

{

    ans+=get(num+)-get(a[now]-);

    gao(b[now],);

    for(int i=h[now];i;i=e[i].nxt)

    {

        dfs(e[i].to);

    }

    gao(b[now],-);

}

int main()

{

    int i,j;

    scanf("%d",&t);

    while(t--)

    {

        ans=;

        tot=;

        j=;

        ll p;

        memset(h,,sizeof h);

        memset(fa,,sizeof fa);

        memset(q,,sizeof q);

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

        rep(i,,n){

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

            if(a[i]==)b[i]=1e19;

            else b[i]=p/a[i];

            c[j++]=a[i],c[j++]=b[i];

        }

        sort(c,c+j);

        num=unique(c,c+j)-c;

        rep(i,,n)a[i]=lower_bound(c,c+num,a[i])-c+,b[i]=lower_bound(c,c+num,b[i])-c+;

        rep(i,,n-)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            add(x,y);

            fa[y]=x;

        }

        rep(i,,n)if(!fa[i])dfs(i);

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

    }

    //system("Pause");

    return ;

}

秒客网

2016大连网络赛 Weak Pair

Weak Pair

相关文章