Cerinta completa

A pair of nodes, , is a similar pair if the following conditions are true:

  1. node is the ancestor of node

Given a tree where each node is labeled from to , find the number of similar pairs in the tree.

For example, given the following tree:

image

We have the following pairs of ancestors and dependents: 

Pair	abs(a-b)	Pair	abs(a-b)
1,2	1		3,4	1
1,3	2		3,5	2
1,4	3		3,6	3
1,5	4
1,6	5

If for example, we have pairs that are similar, where .

Function Description

Complete the similarPair function in the editor below. It should return an integer that represents the number of pairs meeting the criteria.

similarPair has the following parameter(s):

  • n: an integer that represents the number of nodes
  • k: an integer
  • edges: a two dimensional array where each element consists of two integers that represent connected node numbers

Input Format

The first line contains two space-separated integers and , the number of nodes and the similarity threshold.
Each of the next lines contains two space-separated integers defining an edge connecting nodes and , where node is the parent to node .

Constraints

Output Format

Print a single integer denoting the number of similar pairs in the tree.

Sample Input

5 2
3 2
3 1
1 4
1 5

Sample Output

4

Explanation

image
The similar pairs are , , , and , so we print as our answer.
Observe that and are not similar pairs because they do not satisfy for .

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    static class Fenwick {
        int n;
        int[] bit;
        Fenwick(int n) { this.n = n; bit = new int[n + 2]; }
        void add(int idx, int delta) {
            for (int i = idx; i <= n; i += i & -i) bit[i] += delta;
        }
        int sum(int idx) {
            int s = 0;
            for (int i = idx; i > 0; i -= i & -i) s += bit[i];
            return s;
        }
        int range(int l, int r) {
            if (l > r) return 0;
            if (l < 1) l = 1;
            if (r > n) r = n;
            if (l > r) return 0;
            return sum(r) - sum(l - 1);
        }
    }

    static class Frame {
        int u;
        boolean exit;
        Frame(int u, boolean exit) { this.u = u; this.exit = exit; }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int k = fs.nextInt();

        @SuppressWarnings("unchecked")
        ArrayList<Integer>[] children = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) children[i] = new ArrayList<>();
        int[] indeg = new int[n + 1];

        for (int i = 0; i < n - 1; i++) {
            int p = fs.nextInt();
            int c = fs.nextInt();
            children[p].add(c);
            indeg[c]++;
        }

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

        Fenwick fw = new Fenwick(n);
        long ans = 0;

        ArrayDeque<Frame> st = new ArrayDeque<>();
        st.push(new Frame(root, false));

        while (!st.isEmpty()) {
            Frame f = st.pop();
            int u = f.u;
            if (f.exit) {
                fw.add(u, -1);
                continue;
            }

            ans += fw.range(u - k, u + k);
            fw.add(u, 1);

            st.push(new Frame(u, true));
            ArrayList<Integer> ch = children[u];
            for (int i = ch.size() - 1; i >= 0; i--) {
                st.push(new Frame(ch.get(i), false));
            }
        }

        System.out.println(ans);
    }
}

Scor obtinut: 1.0

Submission ID: 464619688

Link challenge: https://www.hackerrank.com/challenges/similarpair/problem

Similar Pair