Another Tree with Number Theory Solution Codechef

Another Tree with Number Theory Solution February Challenge 2021

You are given a rooted tree with NN nodes (numbered 11 through NN; node 11 is the root). For each ii (1≤i≤N−11≤i≤N−1), the parent of the node i+1i+1 is pipi.

You need to answer QQ queries. (Sounds quite familiar!) For each query, first, WW tasks are given to node VV. These tasks are processed in the tree in the following way:

  • When a node receives aa tasks and it has no children, all aa tasks are executed by this node.
  • Otherwise, i.e. if the node has K>0K>0 children, where KK is a divisor of aa, then this node gives a/Ka/K of these tasks to each of its children. This process is performed recursively by each child on the tasks it receives.
  • Otherwise, i.e. if the node has K>0K>0 children, but KK is not a divisor of aa, all aa tasks are ignored and none of this node’s children receive any tasks.

For each query, find the number of tasks that are not executed, i.e. end up ignored, possibly after passing down the tree.

Also See: February Long Challenge 2021 Solutions

Input

  • The first line of the input contains a single integer NN.
  • The second line contains N−1N−1 space-separated integers p1,p2,…,pN−1p1,p2,…,pN−1.
  • The third line contains a single integer QQ.
  • QQ lines follow. Each of these lines contains two space-separated integers VV and WW describing a query.

Output

For each query, print a single line containing one integer ― the number of tasks that are not executed.

Constraints

  • 1≤N,Q≤1051≤N,Q≤105
  • 1≤pi≤N1≤pi≤N for each valid ii
  • the graph described on the input is a tree
  • 1≤V≤N1≤V≤N
  • 1≤W≤1061≤W≤106

Subtasks

Subtask #1 (20 points): N≤100N≤100

Subtask #2 (80 points): original constraints

Example Input

5
1 1 2 2
2
1 10
1 20

Example Output

5
0

Follow us on telegram for quick update an abundance of free knowledge: Click Here

Solution

Program C:

#include <stdio.h>
int y=0;
int des(int a[1000000],int n,int u,int v){
    int x=0,z;
    for(int i=1;i<=n;i++){
        if(a[i]==u){
            x++;    
        }
    }
    if(x==0){
        return 0;}
    if(((v/x)*x)==v){
        for(int i=1;i<=n;i++){
            if(a[i]==u){
                des(a,n,i,v/x);
            }
        }
    }
    else{
        y=y+v;
    }
}
int main() {
	int i,j,k,l,n,m,a[1000000],u,v;
	scanf("%d",&n);
	for(i=2;i<=n;i++){
	    scanf("%d",&a[i]);
	}
	a[1]=-1;
	scanf("%d",&m);
	for(i=0;i<m;i++){
	    scanf("%d%d",&u,&v);
	    y=0;
	    des(a,n,u,v);
	    printf("%d\n",y);
	}
	return 0;
}

Program C++:

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long int ll;
int n = 1;
const int mv = 2e5 + 2;
vector<int> g[mv];
int ansarr[mv];
int leaf[mv];
vector<pair<int,int>> queriesarr[mv];
unordered_map<int,vector<int>*>  level[mv];
void leafnodedfs(int u){
    if(g[u].size()==0){
        leaf[u]=1;
    }
    for(auto i:g[u]){
        leafnodedfs(i);
        
        leaf[u]+=leaf[i];
    }
}
void merge(int x,int y){
    if(queriesarr[x].size()<queriesarr[y].size()){
        swap(queriesarr[x],queriesarr[y]);
    }
    for(auto i:queriesarr[y]){
        queriesarr[x].push_back(i);
    }
}


void dfs(int u,int lvl){
    if(g[u].size()==0||leaf[u]==1){
        return;
    }
    int sz = g[u].size();
    
    if(g[u].size()==1){
        merge(g[u][0],u);
        swap(level[lvl+1],level[lvl]);
    }
    else {
        for (auto &i:level[lvl]) {
            if (i.f % sz != 0) {
                
                auto v=*i.s;
                for(auto x:v) {
                    ansarr[x] += i.f;
                }
            } else {
                level[lvl+1][i.f/sz]=i.s;
            }
        }
        for (auto &i:queriesarr[u]) {
            if (i.f % sz != 0) {
                
                ansarr[i.s] += i.f;
            } else {
                if(level[lvl+1].count(i.f/sz)==0){
                    level[lvl+1][i.f/sz]=new vector<int>();
                }
                level[lvl+1][i.f/sz]->push_back(i.s);
            }
        }
    }
    
    for(auto i:g[u]){
        dfs(i,lvl+1);
    }
    if(g[u].size()==1){
        swap(level[lvl+1],level[lvl]);
    }
    else{
        for (auto &i:queriesarr[u]) {
            
            if (i.f % sz != 0) {
            } else {
                level[lvl+1][i.f/sz]->pop_back();
            }
        }
    }
    level[lvl+1].clear();
}


void ansbtao() {
    cin>>n;
    for(int i=0; i<n-1; i++){
        int ele;
        cin>>ele;
        g[ele].push_back(i+2);
    }
    
    leafnodedfs(1);
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        ll v,k;
        cin>>v>>k;
        queriesarr[v].push_back({k,i});
    }
    dfs(1,1);
    
    for(int i=0; i<q; i++){
        cout<<ansarr[i]<<endl;
    }
}
int main(){
        ios_base::sync_with_stdio(false);
          cin.tie(NULL);
          cout.tie(NULL);
    
         ansbtao();
    
}

Program Java:

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

class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        HashMap<Integer, ArrayList<Integer>> mapTree = new HashMap<>();
        mapTree.put(1,new ArrayList<>());

        for(int i=2;i<=n;i++){
            int num = scanner.nextInt();
            mapTree.get(num).add(i);
            mapTree.put(i,new ArrayList<>());
        }

        int q = scanner.nextInt();

        for(int i=0;i<q;i++){
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            findAnswer(mapTree,v,w);
            System.out.println(w- completed);
            completed = 0;
        }
	}
	
	static int completed = 0;


    public static void findAnswer(HashMap<Integer,ArrayList<Integer>> mapTree, int curr, int w){

        if(mapTree.get(curr).size()==0){
            completed +=w;
            return;
        }

        if(w%(mapTree.get(curr).size())!=0){
            return;
        }


        int division = w/mapTree.get(curr).size();

        for(int i=0;i<mapTree.get(curr).size();i++){
            findAnswer(mapTree,mapTree.get(curr).get(i),division);
        }

    }
	
}

Program Python:

class Node():
    def __init__(self, value):
        self.data = value
        self.child = []

def insert_node(head, parent, value):
    if head == None:
        return
    if head.data == parent:
        temp = Node(value)
        head.child.append(temp)
        return
    for i in range(len(head.child)):
        insert_node(head.child[i],parent,value)

def find_node(head, node_value):
    if head.data == node_value:
        return head
    else:
        for i in range(len(head.child)):
            temp1 = find_node(head.child[i], node_value)
            if temp1 != None:
                return temp1

def traverse(head):
    if head == None:
        return
    print(head.data)
    for i in range(len(head.child)):
        traverse(head.child[i])

def calculate(head, k, l):
    if len(head.child) == 0:
        l.append(k)
        return 
    else:
        length = len(head.child)
        if k % length == 0:
            for i in range(length):
                calculate(head.child[i], k//length, l)

no = int(input())
parent = list(map(int, input().split()))
q_no = int(input())
l = []
head = Node(1)
for i in range(len(parent)):
    insert_node(head, parent[i], i+2)

for z in range(q_no):
    l.clear()
    arr = list(map(int,input().split()))
    temp = find_node(head, arr[0])
    l.append(0)
    calculate(temp,arr[1],l)
    print(arr[1]-sum(l))

Codechef Long Challenges

September Long Challenge 2021 Solution

February Long Challenge 2021

Leave a Comment