Coprime Paths
You are given an undirected, connected graph, , with nodes and edges where . Each node is initially assigned a value, , that has at most prime divisors.
You must answer queries in the form u v. For each query, find and print the number of pairs of nodes on the path between and such that and the length of the path between and is minimal among all paths from to .
Input Format
The first line contains two space-separated integers describing the respective values of and .
The second line contains space-separated integers describing the respective values of .
Each of the subsequent lines contains two space-separated integers, and , describing an edge between nodes and .
Each of the subsequent lines contains two space-separated integers, and , describing a query.
Constraints
Output Format
For each query, print an integer on a new line denoting the number of pairs of nodes on the path between and such that and the length of the path between and is minimal among all paths from to .
Sample Input 0
6 5
3 2 4 1 6 5
1 2
1 3
2 4
2 5
3 6
4 6
5 6
1 1
1 6
6 1
Sample Output 0
9
6
0
3
3
Explanation 0
The diagram below depicts graph and the paths specified by each query, as well as the Pair Values for each path in the form :
Recall that, for each queried path, we want to find and print the number of pairs of nodes such that .
xxxxxxxxxxchar* readline();char* ltrim(char*);char* rtrim(char*);char** split_string(char*);int parse_int(char*);int main(){ char** first_multiple_input = split_string(rtrim(readline())); int n = parse_int(*(first_multiple_input + 0)); int q = parse_int(*(first_multiple_input + 1)); char** nodes_temp = split_string(rtrim(readline())); int* nodes = malloc(n * sizeof(int)); for (int i = 0; i < n; i++) { int nodes_item = parse_int(*(nodes_temp + i)); *(nodes + i) = nodes_item; } int** edges = malloc((n - 1) * sizeof(int*)); for (int i = 0; i < n - 1; i++) { *(edges + i) = malloc(2 * (sizeof(int))); char** edges_item_temp = split_string(rtrim(readline())); for (int j = 0; j < 2; j++) { int edges_item = parse_int(*(edges_item_temp + j)); *(*(edges + i) + j) = edges_item; } } for (int q_itr = 0; q_itr < q; q_itr++) { int u = parse_int(ltrim(rtrim(readline()))); int v = parse_int(ltrim(rtrim(readline()))); // Write your code here } return 0;}char* readline() { size_t alloc_length = 1024; size_t data_length = 0; char* data = malloc(alloc_length); while (true) { char* cursor = data + data_length; char* line = fgets(cursor, alloc_length - data_length, stdin); if (!line) { break; } data_length += strlen(cursor); if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; } alloc_length <<= 1; data = realloc(data, alloc_length); if (!data) { data = '\0'; break; } } if (data[data_length - 1] == '\n') { data[data_length - 1] = '\0'; data = realloc(data, data_length); if (!data) { data = '\0'; } } else { data = realloc(data, data_length + 1); if (!data) { data = '\0'; } else { data[data_length] = '\0'; } } return data;}char* ltrim(char* str) { if (!str) { return '\0'; } if (!*str) { return str; } while (*str != '\0' && isspace(*str)) { str++; } return str;}char* rtrim(char* str) { if (!str) { return '\0'; } if (!*str) { return str; } char* end = str + strlen(str) - 1; while (end >= str && isspace(*end)) { end--; } *(end + 1) = '\0'; return str;}char** split_string(char* str) { char** splits = NULL; char* token = strtok(str, " "); int spaces = 0; while (token) { splits = realloc(splits, sizeof(char*) * ++spaces); if (!splits) { return splits; } splits[spaces - 1] = token; token = strtok(NULL, " "); } return splits;}int parse_int(char* str) { char* endptr; int value = strtol(str, &endptr, 10); if (endptr == str || *endptr != '\0') { exit(EXIT_FAILURE); } return value;}