Invitation for Encoding JAN'20

general
28

Can someone check what is wrong in this code. It keeps on giving SIGSEGV. :frowning_face:
Problem Code

29

Can you explain the approach real quick?

30

The data vector for each node stores the updates and queries(also including the time 0 update for all the nodes). Then I’ve built a segment tree on query positions (i.e the time at which this query was done). Basically it stores all the updates of the current active branch from the root to the current node. On completing dfs for a particular node, I remove those updates from the segment tree.

31

The runtime error is because of this-
int val[n];
cin>>n>>q;

You are declaring the array before taking n as input.

2 Likes
32

And here is a testcase on which your code fails-

4 1
1 2
1 3
2 4
1 2 3 4
1 2

Your code outputs 9 (after removing the runtime error) whereas answer is 2 i guess

2 Likes
33

You can see my approach for this problem.
I have pre-processed the value for every node [of traversal from Xth node to Root node] using optimized LCA search (Binary Lifting), then I used sub tree queries along with lazy propagation of segment trees to get the desired result.

Simple code : here

1 Like
34

Thanks brother.

1 Like
35

what was the approach to solve ECJAN20H?

1 Like
36

Why did you use lca for the initializing nodes? cant we do it by a simple dfs? Is the lca helping in some way?

1 Like
37

I felt it to be a direct algorithm problem. Hence, used LCA.
No additional help, just a method, I used. :stuck_out_tongue:

1 Like
38

:sweat_smile::smiley: So we can use a simple dfs instead as well ?

1 Like
39

hey can you explain you code, i am not able to understand how you used the segment tree without making chains, I am only aware about HLD

40

There is no need of HLD here. Just think, if you update a node, it affects only the answer of nodes in the subtree of that node, so using the euler tricks & segment tree is sufficient for this problem!

41

I am confused with the query part,

how it is computing the answer for only those nodes which are in the path and neglecting other nodes in the path either left or right child

1 Like
42

First thing first. Learn about eulerian path on tree. If we use that trick, we can access only the nodes of a particular subtree we desire.
In other words, we convert the tree into an array, then you segment tree on the array.

43

@nuttela Waiting for editorials, if posted can you provide link? :slightly_smiling_face:

1 Like
44

We don’t need lazy prop here right?

46

Use tries.

47

No it should work without lazy prop.

48

I only know how to do it with lazy prop. Is there any other way ?