Traversing Trees Solutions CENS20F

Traversing Trees Solutions

You are given a tree established at hub 1 with N vertices. The ith vertex at first has esteem Ai(1≤i≤N). You are additionally given Q questions. 

In each inquiry you are given a vertex V. Let S={S1,S2,…Sx} mean the arrangement of vertices with the end goal that Si is in the subtree of V, separation among Si and V is even and Si≠V for all I. For all Si , add ASi to AV and change the estimation of ASi to zero. 

Discover the estimations of all the vertices after all inquiries are performed. 

Note-The separation between two vertices is characterized as the quantity of edges crossed on the most brief way from one vertex to the next. 

 

Info: 

The principal line contains a number T meaning the quantity of experiments. 

The principal line of each experiment contain two whole numbers N and Q. 

The subsequent line contains N space isolated numbers, A1,A2,…,An signifying the underlying estimations of the vertices. 

The following N−1 lines contain two numbers u and v indicating an edge between uand v. 

The following Q lines contain a solitary number which is the inquiry. 

Yield:Print a solitary line containing N numbers for each experiment which is the last estimations of the vertices. 

 

Limitations: 

1≤T≤10 

1≤N≤200000 

1≤Q≤200000 

0≤Ai≤109 

The aggregate of N over all experiments doesn’t surpass 200000. 

The aggregate of Q over all experiments doesn’t surpass 200000. 

 

Test Input 

4 3 

6 2 7 3 

1 2 

2 3 

3 4 

 

Test Output 

13 5 0 

 

Clarification 

Hub 3 has no youngster in its subtree which is at an even separation so there is no adjustment in the qualities. Estimations of hubs after first inquiry: 6,2,7,3. 

Hub 4 is at an even separation in the subtree of hub 2 so A4 gets added to A2 and A4 gets 0. Estimations of hubs after second question: 6,5,7,0. 

Hub 3 is at an even separation in the subtree of hub 1 so A3 gets added to A1 and A3 gets 0. Estimations of hubs after third question: 13,5,0,0.

 

Solution

import java.util.*;

import java.lang.*;

import java.io.*;

 

/* Name of the class has to be “Main” only if the class is public. */

class Codechef

{

    public static void main (String[] args) throws java.lang.Exception

    {

        // your code goes here

        FastReader fr=new FastReader();

        StringBuilder sb=new StringBuilder();

        int t=fr.nextInt();

        while(t–>0)

        {

            int n=fr.nextInt(),q=fr.nextInt(),i,d[]=new int[n];

            long a[]=new long[n];

            ArrayList<Integer> g[]=new ArrayList[n];

            for(i=0;i<n;i++)

                g[i]=new ArrayList<>();

            for(i=0;i<n;i++)

                a[i]=fr.nextInt();

            for(i=0;i<n-1;i++)

            {

                int l=fr.nextInt()-1,r=fr.nextInt()-1;

                g[l].add(r);

                g[r].add(l);

            }

 

            boolean v[]=new boolean[n];

            Queue<Integer> qu=new LinkedList<>();

            Queue<Integer> de=new LinkedList<>();

            qu.add(0); de.add(0);

            v[0]=true;

            while(!qu.isEmpty())

            {

                int p=qu.poll(),dp=de.poll();

                d[p]=dp;

                for(int x:g[p])

                if(!v[x])

                {

                    v[x]=true;

                    qu.add(x);

                    de.add(dp+1);

                }

            }

 

            ArrayList<Pair> odd=new ArrayList<>(),even=new ArrayList<>();

            Set<Integer> set=new HashSet<>();

            while(q–>0)

            {

                int x=fr.nextInt()-1;

                set.add(x);

            }

            for(int x:set)

            {

                if(g[x].size()==1 && x!=0) continue;

                if(d[x]%2==1) odd.add(new Pair(x,d[x]));

                else even.add(new Pair(x,d[x]));

            }

            boolean v1[]=new boolean[n],v2[]=new boolean[n];

            sort(odd); sort(even);

 

            for(i=0;i<odd.size();i++)

            if(!v1[odd.get(i).i])

            {

                int cur=odd.get(i).i;

                long tot=0;

                qu.add(cur);

                v1[cur]=true;

                while(!qu.isEmpty())

                {

                    int p=qu.poll();

                    if(d[p]%2==1)

                    {

                        tot+=a[p];

                        a[p]=0;

                    }

                    for(int x:g[p])

                    if(d[x]>d[p])

                    {

                        v1[x]=true;

                        qu.add(x);

                    }

                }

                a[cur]=tot;

            }

 

            for(i=0;i<even.size();i++)

            if(!v2[even.get(i).i])

            {

                int cur=even.get(i).i;

                long tot=0;

                qu.add(cur);

                v2[cur]=true;

                while(!qu.isEmpty())

                {

                    int p=qu.poll();

                    if(d[p]%2==0)

                    {

                        tot+=a[p];

                        a[p]=0;

                    }

                    for(int x:g[p])

                    if(d[x]>d[p])

                    {

                        v2[x]=true;

                        qu.add(x);

                    }

                }

                a[cur]=tot;

            }

 

            for(i=0;i<n;i++)

                sb.append(a[i]+” “);

            sb.append(“n”);

        }

        System.out.print(sb);

    }

 

    static class Pair

    {

        int i,d;

        Pair(int a,int b)

        {

            i=a;

            d=b;

        }

    }

 

    static void sort(ArrayList<Pair> a)

    {

        Collections.sort(a, new Comparator<Pair>() {

            @Override

            public int compare(Pair o1, Pair o2) {

                if(o1.d>o2.d) return 1;

                else if(o1.d==o2.d) return o1.i>=o2.i?1:-1;

                else return -1;

            }});

    }

 

    static class FastReader

    {

        final private int BUFFER_SIZE=1<<16;

        private DataInputStream dis;

        private byte[] buffer;

        private int bufferPointer,bytesRead;

 

        public FastReader()

        {

            dis=new DataInputStream(System.in);

            buffer=new byte[BUFFER_SIZE];

            bufferPointer=bytesRead=0;

        }

 

        public int nextInt() throws IOException

        {

            int ret=0;

            byte c=read();

            while(c<=’ ‘) c=read();

            boolean neg=(c==’-‘);

            if(neg) c=read();

            do

            {

                ret=ret*10+c-‘0’;

            }while((c=read())>=’0′ && c<=’9′);

            if(neg) return -ret;

            return ret;

        }

 

        private void fillBuffer()throws IOException

        {

            bytesRead=dis.read(buffer,bufferPointer=0,BUFFER_SIZE);

            if(bytesRead==-1) buffer[0]=-1;

        }

        private byte read() throws IOException

        {

            if(bufferPointer==bytesRead) fillBuffer();

            return buffer[bufferPointer++];

        }

    }

}

November Challenge 2020 SOLUTION CodeChef

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

Leave a Comment