Beautiful Tree — An interview question

Revision en1, by dgupta0812, 2020-07-29 23:55:25

Hey guys !!

Hope you all are in good condition and enjoying the lock down (if there's one in your region) :):)

I accidentally stumbled upon a question of trees and online queries which I am unable to solve. I'm attaching the image containing the question. And just in case if it's not clear

You are given a tree with N vertices, rooted at vertex 1 (indexed from 1 to N). Each vertex has a value associated with it. The value of $$$i_{th}$$$ vertex is $$$a_i$$$. Consider $$$f_i$$$ as the $$$a_i$$$ th beauftiful number.

A beautiful number is a number whose sum of squares of digits is less than or equal to X. You have to process M queries where each query can be

Type 1 -> 1 i y : update $$$a-i$$$ to y

Type 2 -> 2 i : output the sum of $$$f_i$$$ for all the nodes in the sub-tree of node i ( including node i). Since the number can be very large compute it modulo 998244353.

CONSTRAINTS :

1 <= N, M, i, $$$u_i$$$, $$$v_i$$$, $$$a_i$$$, y <= 5*$$$10^5$$$

1 <= X <= $$$10^{10}$$$

Tags #trees, #range query, #range-trees, #online, #interview, #problem, #help me, #algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English dgupta0812 2020-12-24 09:11:38 7 Tiny change: 'Beautiful ' -> '[HELP] Beautiful '
en4 English dgupta0812 2020-12-24 09:10:34 7
en3 English dgupta0812 2020-07-30 00:24:09 70
en2 English dgupta0812 2020-07-30 00:16:45 660 Tiny change: 'Hey guys !' -> 'Your title here...\n==================\nHey guys !' (published)
en1 English dgupta0812 2020-07-29 23:55:25 1044 Initial revision (saved to drafts)