# Traversing Trees Solutions CENS20F

Page Contents

## 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

{

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;

}

boolean v[]=new boolean[n];

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;

}

}

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

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

while(q–>0)

{

int x=fr.nextInt()-1;

}

for(int x:set)

{

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

}

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;

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;

}

}

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;

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;

}

}

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;

}});

}

{

final private int BUFFER_SIZE=1<<16;

private DataInputStream dis;

private byte[] buffer;

{

dis=new DataInputStream(System.in);

buffer=new byte[BUFFER_SIZE];

}

public int nextInt() throws IOException

{

int ret=0;

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

do

{

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

if(neg) return -ret;

return ret;

}

private void fillBuffer()throws IOException

{

}

{

return buffer[bufferPointer++];

}

}

}