CENS20F - Editorial

editorial
, ,
2

Thanks for providing such a neat code, setters rarely provide such a readable and documented code, btw idea of squeezing everything in a single dfs is really cool

MY solution 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pb push_back 
#define vi vector
#define FOR(i,l,n) for(int i=l;i<n;i++)
#define EACH(x,a) for(auto x:a)
const long mxN =2e5+2 ;
int n,q,a[mxN],a1[mxN],a2[mxN] ,d[mxN],ans[mxN];
vi<int> adj[mxN];
void dfs1(int v=1,int p=0){
  if(v>1)d[v]=d[p]+1 ;
  a2[v]=d[v]&1?a[v]:0 ;a1[v]=d[v]&1?0:a[v] ;
  EACH(x,adj[v])
    if(x^p)
      dfs1(x,v),a1[v]+=a1[x],a2[v]+=a2[x];
}
set<int>e,o ;
void dfs2(int v=1,int p=0,bool ok1=0,bool ok2=0){
  if(d[v]&1^1){
    if(ok1)
      ans[v]=0;
    else{
      ans[v]=a[v] ;
      if(e.count(v))
        ok1=1 ,ans[v]=a1[v] ;
    }    
  }else{
    if(ok2)
      ans[v]=0;
    else{
      ans[v]=a[v] ;
      if(o.count(v))
        ok2=1 ,ans[v]=a2[v] ;
    }    
  }
  EACH(x,adj[v])
    if(x^p)
      dfs2(x,v,ok1,ok2) ;
}
void solve(){ 
  cin >>n>>q ;
  FOR(i,1,n+1)
    cin >> a[i] ;
  FOR(i,0,n-1){
    int a,b ;cin>>a>>b ;
    adj[a].pb(b);adj[b].pb(a) ;
  }
  dfs1() ;
  while(q--){
    int x;cin >> x ;
    if(d[x]&1)
      o.insert(x);
    else
      e.insert(x);
  }
  dfs2() ;
  FOR(i,1,n+1)
    cout << ans[i] <<" " ;
  cout << "\n" ;
  FOR(i,1,n+1)
    adj[i].clear(),d[i]=0,ans[i]=0 ;
  e.clear();o.clear() ;
}
signed main() {
  int t;cin >>t ;
  while(t--)
    solve();
}
1 Like
3

What is wrong with this → CodeChef: Practical coding for everyone
Please help someone .I used BFS and used checked array to prevent from visiting tree with all 0s.

4

I wrote a solution but got stuck since I couldn’t see what went wrong here. Can someone provide a simple test case so that I realize my mistake here?

My approach: Calculate the depth of each node using a BFS (considering root to be at depth 0), and then create a list of each node corresponding to it’s depth, so that the list nodeAtDepth[i] tells us what nodes are there at depth i.

Then, for each query V, consider all nodes k at distance depth[V] + 2y and add A[k] to A[V], and set A[k] to 0. If I find a depth which I’ve already visited before, all of those values must have been set to 0 and so I can discard it.

Link to my solution

5

We can created a separate forest from the given tree, with edges connecting node to its grand parent.

6

Can you share the editorial of Cherry and Squares

7

It is not fully prepared. Will post it by tomorrow. :slight_smile:

8

Consider this case
1
8 1
1 1 1 1 1 1 1 1
1 2
2 3
3 4
4 7
2 5
5 6
6 8
5
If two nodes are at different even depths it doesn’t necessarily mean that one is in the subtree of the other.
Your output - 1 1 1 1 3 1 0 0
Correct output - 1 1 1 1 2 1 1 0

3 Likes
10

Okay thanks.

11

Don’t know why getting Tle … i think its a O(n) solution. ti would be great help if someone help me finding the reason .
https://www.codechef.com/viewsolution/37002710

12

Oh dang, that was stupid of me.
Thank you for taking the time to go through it!
I’ll upsolve this tomorrow.

13

Hello, can you tell me on which test-case does my solution fails ?
https://www.codechef.com/viewsolution/37006323
Same idea as that of the editorial.
@aert

14

@aert @cub Can anyone please help me find where my solution fails :CodeChef: Practical coding for everyone
@aryanc403

1 Like
15

I haven’t properly seen your code but it fails on
1
8 3
1 1 1 1 1 1 1 1
1 2
2 3
3 4
4 7
2 5
5 6
6 8
7
3
1
Your output - 4 1 0 1 0 1 0 1
Correct output - 5 1 0 1 0 1 0 0

17

I was coding segment tree along with euler tour. Only Update function was left when I realised one doesn’t need it. :slightly_smiling_face:
“Things to watch out for” Did got one TLE due to this.

2 Likes
19

What is wrong with this → CodeChef: Practical coding for everyone
Please help someone .I used BFS and created a distance array for each Node.

I am getting runtime array but it is working fine for the sample test case.

21

Thanks brother , I was missing a Q.pop() operation when I was using continue statement But after correcting it also I am getting correct answer on your test case but WA during submission. Can you now tell me some test cases where my solution is failing . Thanks in advance.
https://www.codechef.com/viewsolution/37007493

22

Actually your approach is not correct. We have to transfer the values of nodes at even distance to the source node “present in that subtree”.
But according to your approach you are transfering values of all nodes whose depth is even from that node, so there may be some nodes which can not be present in that subtree.

1 Like
24

" You are given a tree rooted at node 1 with N vertices."
This is the first line of the question .

3 Likes
26

Yeah, @aert helped me realize it as well.
Thank you!

27

It passed. My Submission