2016 ACM/ICPC Asia Regional Dalian Online 1010 Weak Pair dfs序+分块

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

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

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

2 3

1 2

Sample Output

题意：给你一颗根树，求有多少点对(u,v) u!=v满足u是v的祖先且点权au*av<=k

思路：问题转化一下，就是求对于每一个点u，以该点为根的子树下，有多少个点v的权值是小于等于(k/au + 1)；由于是子树的问题，那么可以想到的是先求出一个dfs序，将问题转化为区间查询的问题，那么问题就是，对于每个点u，在区间[st[u]+1,ed[u]]有多少个值是小于等于(k/au + 1)；求一个区间有多少个数小于莫个数G的数可以用分块实现，就是完整的块二分，两边的块暴力，复杂度nsqrt(n)

坑点：一直以为1就是root。。。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cmath>

#include <queue>

#include <algorithm>

#include <stack>

#include <queue>

#include <map>

#include <set>

#include <vector>

#include <cstdlib>

using namespace std;

typedef long long ll;

const int maxn = 3e5 + ;

struct Edge {

    int to, nex;

}e[maxn];

int n;

ll k;

ll a[maxn];

int root;

int head[maxn], tot;

void init() {

    memset(head, -, sizeof head);

    tot = ;

}

void add(int u, int v) {

    e[tot].to = v;

    e[tot].nex = head[u];

    head[u] = tot++;

}

ll id[maxn];

int flag[maxn];

void input() {

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

    memset(flag, , sizeof flag);

    for(int i = ; i < n; ++i) scanf("%I64d", &a[i]);

    int u, v;

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

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

        u--; v--;

        flag[v] = ;

        add(u, v);

    }

    for(int i = ; i < n; ++i) if(flag[i] == ) { root = i; break; }

}

int st[maxn], ed[maxn], tim;

void dfs(int u) {

    st[u] = ++tim;

    id[tim] = a[u];

    for(int i = head[u]; ~i; i = e[i].nex) {

        dfs(e[i].to);

    }

    ed[u] = tim;

}

const int SIZE = ;

ll block[maxn / SIZE + ][SIZE + ];

void init2() {

    int b = , j = ;

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

        block[b][j] = id[i];

        if(++j == SIZE) { b++; j = ; }

    }

    for(int i = ; i < b; ++i) sort(block[i], block[i] + SIZE);

    if(j) sort(block[b], block[b] + j);

}

int query(int L, int R, ll v) {

    int lb = L / SIZE, rb = R / SIZE;

    int k = ;

    if(lb == rb) {

        for(int i = L; i <= R; ++i) if(id[i] < v) k++;

    } else {

        for(int i = L; i < (lb + ) * SIZE; ++i) if(id[i] < v) k++;

        for(int i = rb * SIZE; i <= R; ++i) if(id[i] < v) k++;

        for(int b = lb + ; b < rb; ++b) {

            k += lower_bound(block[b], block[b] + SIZE, v) - block[b];

        }

    }

    return k;

}

void solve() {

    tim = -;

    dfs(root);

    init2();

   ll ans = ;

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

        if(st[i] == ed[i]) continue;

        if(a[i] == ) { ans += (ed[i] - st[i]); continue; }

        ll v = k / a[i] + ;

        ans += query(st[i]+, ed[i], v);

   }

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

}

int main() {

#ifdef LOCAL

    freopen("in", "r", stdin);

#endif

int cas;

    while(~scanf("%d", &cas)) {

    //int cas;

        while(cas --) {

            init();

            input();

            solve();

        }

    }

    return ;

}