September 26, 2019 10:34. Looking forward to read corrections/feedback/better solutions in the comment section. who have weight nodes or edges ? It should say "JOI 2015 Railroad but on a line instead of a general tree". It is guaranteed that the sum of $$$k_i$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum\limits_{i=1}^{m} k_i \le 2 \cdot 10^5$$$). The j-th line contains two integers vj,kj (1vjn;1kj105). Tutorial Implementation Essentially, we just nest the loops that one would find in a 1D BIT to get N-dimensional BITs. Do you visit all vertices on simple path for each query? Increase the value of $$$a_i$$$ by $$$X$$$, Find the sum of $$$a_i$$$ on the path from $$$u$$$ to $$$v$$$ for 2 nodes $$$u$$$ and $$$v$$$. Programming competitions and contests, programming community . tree , queries on tree , qtree 0 LashaBukhnikashvili 9 years ago 7 Comments (7) Write comment? The answer is "YES" as you can choose the path to the vertex $$$u=5$$$ and all vertices of the query belong to this path. Then when we want to find the value of the element at $$$C$$$, we simply query the sum of $$$BIT[i]$$$ for each $$$i$$$ from 0 to $$$C$$$. $$$2$$$ $$$v$$$ ($$$1 \leq v \leq n$$$), representing a second-type operation. The tree root is a vertex with number 1. Can't you calculate the sum of ranges along with binary lifting? How to do fractional cascading on an iterative segment tree. . In addition, none of these paths should intersect with another. Usually this quadratic loop should be optimized using some data structure, but naive implementatoom also gives $$$O(n\log n)$$$ cache miss. Note: Whenever I talk about edge $$$(u, v)$$$ in this post, I assume that $$$u$$$ is the parent of $$$v$$$. The root of the tree is a vertex number $$$1$$$. CodeForces 877E, Tree Queries and Data Structures - YouTube Powered by Discourse, best viewed with JavaScript enabled, Tree Queries Codecraft IIITH 2015 on Codeforces. Happy coding! Notice how there is a path from $$$u$$$ to $$$v$$$ if and only if the sum of edges on the path between $$$u$$$ and $$$v$$$ is 0. If $$$r = 1$$$, the values of vertices $$$2$$$, $$$4$$$ and $$$5$$$ get increased. Do the tests include a case in which an $$$O(nq)$$$ approach will incur close to the worst case of $$$10^{10}$$$ function evaluations? Don't get it wrong: if we iterate over a path just, for example, by going from both endpoints towards the root, it gets tl (even with pragmas): submission. CFTracker And it works ~3 sec on CF on the worst case. Vertices are numbered from $$$1$$$ to $$$n$$$. September 26, 2019 10:38. Heavy-Light Decomposition USACO Guide Input The first line contains two integers n and m (2 n 105; 1 m 105). Summer 2018, Xi Lin Contest 4: HDU. If $$$r = 3$$$, the values of vertices $$$1$$$, $$$2$$$, $$$4$$$ and $$$5$$$ get increased. 2), Teams going to ICPC WF 2023 (Egypt 2023, 2nd final) WIP List, Atcoder problem statement of F Cans and Openers, Invitation to SmallForces Monthly Contest #3, How do I get blue in codeforces in 1 month, Educational Codeforces Round 152 Editorial, How to solve http://www.spoj.com/problems/SUMMUL/, Educational Codeforces Round 144 Editorial, UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312) Announcement. Multidimensional arrays shall always be accessed by first iterating over the right-most index. You're given a tree with $$$N$$$ nodes. Hope this trick is not a mutual knowledge (though it's definitely not a common knowledge). The only programming contests Web 2.0 platform, http://en.wikipedia.org/wiki/Tree_(graph_theory). (URGENT ANSWER Reqd., TY!) 2), Teams going to ICPC WF 2023 (Egypt 2023, 2nd final) WIP List, Atcoder problem statement of F Cans and Openers, Invitation to SmallForces Monthly Contest #3, How do I get blue in codeforces in 1 month, Educational Codeforces Round 152 Editorial, How to solve http://www.spoj.com/problems/SUMMUL/, Educational Codeforces Round 144 Editorial, UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312) Announcement. Each query contains $$$5$$$ integers: $$$x$$$, $$$y$$$, $$$a$$$, $$$b$$$, and $$$k$$$. The i i -th query consists of the set of ki k i distinct vertices vi[1],vi[2], ,vi[ki] v i [ 1], v i [ 2], , v i [ k i]. Can you please briefly explain how it would work? I think it's about dsu on tree https://codeforces.com/blog/entry/44351. Programming competitions and contests, programming community. How to do fractional cascading on an iterative segment tree? If that is another simpler solution since you only need to have the time of entry of each node in the DFS and the time of exit. dolphingarlic I think there is a typo. The answer is "YES" as you can choose the path from the root $$$1$$$ to the vertex $$$u=10$$$. With it we can build a tree with O ( log) depth with the same maximums on all paths (in each boruvka iteration create a new vertex for all connected components and connect it to all vertices (not initial vertices, but connected components at the start of current boruvka iteration) with weights of edges that you add to MST on current iteration). 1569C - Jury Meeting: Not able to calculate n! Let $$$M = 998244353$$$, it can be shown that the expected value can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. For the second query, where $$$v = 2$$$ and $$$d = 2$$$: Hence, the expected values of all vertices after this query are ($$$2.2, 2.4, 2, 2, 2$$$). - (n!/(k+1), Competitive Programming Roadmap (target: [gray, blue]), Codeforces Round 887 (Div 1, Div 2) Tutorial. My solution used this technique with $$$O(\sqrt{n})$$$ for update and $$$O(\sqrt{n}$$$ $$$log$$$ $$$n)$$$ to get answer. Let the value of each edge in the tree initially be 0. Always try to remember which those are. The add function will simply add the value of the position and subsequently update the answer variable. Codeforces. If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive. If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive. It is supported only ICPC mode for virtual contests. All edges are bidirectional and distinct. The problem Ball Machine from BOI2013 can be solved using a similar idea. . Problem link: Problem - D - Codeforces Explanation : https://youtu.be/SOhZqL6HPjQ Company Queries I bicsi - Codeforces Simion - Codeforces PDF Codeforces #172 Tutorial dolphingarlic or someone: What exactly is being done here (in the solution for Problem 1)? The answer to query vj,kj is the number of such colors of vertices x, that the subtree of vertex vj contains at least kj vertices of color x. Then when we want to find the sum of nodes on the path between node $$$v$$$ and the root, we simply query the sum of $$$b[i]$$$ for each $$$i$$$ from 0 to $$$tin_v$$$. Using binary lifting, we can find the root of any component in $$$O(\log^2 N)$$$ time. But my idea is: since the solution for an X node is going to depend on the solution for all the nodes adjacent to X that are not its father, of course, and the nodes that are at a distance K from the X node are the same to say the number of nodes that meet the condition of parity at a depth = lv (x) + k we can take a map for example to keep the solution for a depth Y in the X subtree. OK I got AC :<. 1 + Div. And for the updates it is logn for each value to be updated.I don't think we can do better than that.This however gives a TLE verdict.Any suggestions? Heavy Light Decomposition (or HLD) supports both operations efficiently. which data structures need problems same as above? During event $$$i$$$, the state of exactly 1 edge is toggled. The next n-1 lines contain the edges of the tree. The following codes calculate sum in the range L L to R R, assuming the segment tree is built after possibly several update queries. Recursive: long long query(int l, int r) { if(l > r)return 0; int node = N + l - 1; int K = min(logs[node & -node], logs[r - l + 1]); return (query(l + (1 << K), r) + seg[node >> K]); } Iterative: Inspired by them, he suddenly came up with an interesting idea for trees in data structures: What if we add another edge in a tree? If $$$r = 5$$$, the values of vertices $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$ get increased. Winter 2019, Jingzhe Tang Contest 1: HDU. Queries on Tree - Codeforces Next $$$q$$$ lines contain five integers $$$x$$$, $$$y$$$, $$$a$$$, $$$b$$$, and $$$k$$$ each ($$$1 \le x,y,a,b \le n$$$, $$$x \ne y$$$, $$$1 \le k \le 10^9$$$) the integers explained in the description. Then we can just list them in array and do a quadratic loop. If that is another simpler solution since you only need to have the time of entry of each node in the DFS and the time of exit. By cache miss I just meant the total size of graph traversed by DFS. I tried to cut off solutions with bad time complexity (what is hard when main complexity is $$$O(n\sqrt{n}$$$ $$$log n)$$$), but I didn't expect this. On the other hand, it's easy to get ac with an $$$O(nq)$$$ solution. 1 + Div. If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive. It is guaranteed that the given edges form a tree. Pay attention This works because node $$$w$$$ only contributes to the sum if $$$w$$$ is an ancestor of $$$v$$$. This allows answering range queries over an array efficiently, while still being flexible enough to allow quick modification of the array. This works because if $$$C$$$ isn't inside the range of an update, the 2 values we update "cancel out" in the query. Usually the solution is built in BFS order and having neighbours' table close to the one you're currently building can be a good improvement. f 0[i][j]: the j-MSS in [0, i]. // qs --> query start index, qe --> query end index int RMQ (node, qs, qe) { if range of node is within qs and qe return value in node else if range of node is completely outside qs and qe return INFINITE else return min ( RMQ (node's left child, qs, qe), RMQ (node's right child, qs, qe) ) } Query. I see that USACO 2015 Max Flow is cited as an additional problem. It is a great problem to learn a variation of traditional segment trees. codesniper99 Does only studying Segment tree cover all Range query questions? (Upon writing this, I realize I should've mentioned this technique in the post as well). We can thus use the same idea we used for the previous problem, but this time, all edges initially have their weight equal to 1 instead of 0. Each query is finding number of weights in level (k + lev[node]) with DFS in-time in the range [in[node], out[node]]. A tree with $$$n$$$ vertices is an undirected connected graph with $$$n-1$$$ edges. Many problems from the Warsaw U contest are from Polish OI Contests, you can found them here. - (n!/(k+1), Competitive Programming Roadmap (target: [gray, blue]), Codeforces Round 887 (Div 1, Div 2) Tutorial. Dynamic Programming on Tree (Complete Series) - CodeChef Discuss If you only update tin[i] instead of both tin[i] and tout[i], you can get the subtree sum by querying the range [tin[i], tout[i]].Consider some path A--B.If you increase tin[A] and tin[B] by 1 and decrease tin[lca(A, B)] by 2, then only nodes on the path A--B get that +1 when you query their subtree sums. We can then use PIE to query subrectangles. Hope you get the point, but you may want to read some articles in Wiki or whatever, to understand it deeply. The first line contains an integer $$$n$$$ ($$$3 \le n \le 10^5$$$), the number of vertices of the tree. All nodes in the merged component will contain all the information stored on the other nodes in the component. 236 lines (210 sloc) 4.21 KB -is-this-fft- [Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges . cdkrot Codeforces Round #516 (by Moscow Team Olympiad) Editorial . Tree Queries (Easy Version) (2200) D2. With the sizes swapped, you are accessing the bytes in sequence (at least in a forward loop, backwards pre-fetching depends on the smartness of the compiler). Edge $$$i$$$ is denoted by two integers $$$u_i$$$ and $$$v_i$$$, the labels of vertices it connects $$$(1 \le u_i, v_i \le n, u_i \ne v_i$$$). 1569C - Jury Meeting: Not able to calculate n! if you don't mind would you please give some hints on how to solve QTREE4? $$$root_u$$$ is the lowest ancestor of $$$u$$$ such that the path from $$$u$$$ to $$$root_u$$$ contains no deactivated edges. How to do fractional cascading on an iterative segment tree. Tree queries for O(nq) - Codeforces Based on the problem we can use a different data structure and modify the add/remove/get_answer functions accordingly. Method quot hdu 1408 acdearm "Money, Money, Money" Codeforces 1467E Distinctive Roots in a Tree Codeforces 1304E. Given a tree with $$$N$$$ nodes, each node $$$i$$$ has a value $$$a_i$$$ that is initially 0. 0:00 / 11:38 CodeForces 877E, Tree Queries and Data Structures Riya Arora 2.91K subscribers Subscribe 2K views 4 years ago Here is the solution for Codeforces 877E which uses a segment tree. You could do that if there are no updates, but I don't think there's an easy way to handle updates without a Fenwick tree, Not to be a pain in the ass or anything but this is the same idea as Mo on trees, Yeah but I think it's kinda nice how this post talks about queries when you add / remove edges from a tree (I don't think that is mentioned in the linked post). You can print each letter in any case (upper or lower). I am surprised, that it makes such a difference. I created a video tutorial explaining the problem. Summer 2018, Ruyi Ji Contest 4: HDU. Interestingly, I got a similar idea here :), Even the problem with $$$n\sqrt n$$$ time complexity was accepted by a $$$n^2$$$ solutionproblem and webmaster's solution. During obtaining the variable, cache levels load into itself not only the variable, but also its memory block, where it belongs. I have been trying to flatten the tree using euler tour and then making a segment tree on the value array for point update and range query . See the fastest solutions here. Never use someone else's code, read the tutorials or communicate with other person during a virtual contest. If $$$r = 3$$$, the values of vertices $$$2$$$, $$$4$$$ and $$$5$$$ get increased. This problem can be solved offline with a tree technique called DSU on tree. Never use someone else's code, read the tutorials or communicate with other person during a virtual contest. That's why, for example, it's way too faster to have a [2][2][10][1000] array in a DP task instead of [1000][10][2][2]. The problem statement has recently been changed. Naive DFS will have $$$O(n^2)$$$ cache miss. We can then apply the above idea and solve this problem in $$$O(M \log N)$$$ time. Any help will be appreciated very much :), I didn't understand clearly. Subordinates This can be solved using basic DP approach in linear time. Following is algorithm to get the minimum. Virtual contest is a way to take part in past contest, as close as possible to participation on time. Instead of solving it by himself, he's going to test you by providing queries on 1-trees. Winter 2013, JAG Autumn 2012: AtCoder. Tree This problem can also be solved using segment trees with range minimum queries as well. If you increase tin[A] and tin[B] by 1 and decrease tin[lca(A, B)] by 2, then only nodes on the path A--B get that +1 when you query their subtree sums. In your code, you have lots of hot loops iterating from 1 to 16 or similar. You are given $$$m$$$ queries. Support the following 2 types of operations in $$$O(\log N)$$$ time: First, we flatten the tree using a preorder traversal. If $$$r = 2$$$, the values of all vertices get increased. Path max queries on a tree in O(1) - Codeforces Excuse me, I didn't understand why your solution is faster than $$$O(nm)$$$. SD Segment Tree Variation, A Shorter And More Efficient - Codeforces Recent codechef long challenge had a task about queries on paths inside a tree: short, given a tree, each vertex contains a linear function, and given $$$q$$$ queries of types "add given linear $$$f$$$ to all vertices of the path between $$$u$$$ and $$$v$$$" and "calculate maximum of $$$f(z)$$$ where $$$z$$$ is given and $$$f$$$ is a function in any of vertices on the path between given $$$u$$$ and $$$v$$$", $$$n$$$ and $$$q$$$ are $$$\leq 10^5$$$, time limit is 4s. . Next line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$), the number of queries Gildong wants to ask. I've come across several problems that require you to be able to efficiently find the sum of some values on a path from $$$A$$$ to $$$B$$$ in a tree. If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive. Since each node in a component has the same amount of information, we can just store that amount in the "root" (i.e. You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree_ (graph_theory). If you're familiar with LCA, you'll know that node $$$u$$$ is an ancestor of node $$$v$$$ if and only if $$$tin_u \leq tin_v$$$ and $$$tout_u \geq tout_v$$$. The image below shows the tree in the example: For the first query, where $$$v = 1$$$ and $$$d = 1$$$: Hence, the expected values of all vertices after this query are ($$$1, 0.4, 0.8, 0.4, 0.4$$$). Then we only need to join the solution of all the nodes adjacent to X as the solution of X and since the problem can be done offline we can find all the solutions as we calculate the solutions for each node. I believe the latter is about 10-20x faster. Segment Tree | Range Minimum Query - GeeksforGeeks Now, Hanh performs q operations, each is either of the following types: Type 1: Hanh selects a vertex v and an integer d. Minimize diameter of tree by applying almost k.operations. Heavy light decomposition (with Segment tree) problem for beginners : http://acm.timus.ru/problem.aspx?space=1&num=1553 If you need the code, you can see my code: https://sites.google.com/site/kc97ble/container/heavylight-cpp, The only programming contests Web 2.0 platform, Editorial of Codeforces Round 889 (Div. I hope you've learned something from this tutorial. Each of the next $$$n-1$$$ lines describes an edge of the tree. E. 1-Trees and Queries time limit per test 4 seconds memory limit per test 512 megabytes input standard input output standard output Gildong was hiking a mountain, walking by millions of trees. Also maintain a list of nodes for each level in the order in which they appear during the DFS. 2), Teams going to ICPC WF 2023 (Egypt 2023, 2nd final) WIP List, Atcoder problem statement of F Cans and Openers, Invitation to SmallForces Monthly Contest #3, How do I get blue in codeforces in 1 month, Educational Codeforces Round 152 Editorial, How to solve http://www.spoj.com/problems/SUMMUL/, Educational Codeforces Round 144 Editorial, UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312) Announcement. If anything is unclear, please let me know in the comments below. The fifth and the sixth queries both have answer "NO" because you cannot choose suitable vertex $$$u$$$. The only programming contests Web 2.0 platform, Editorial of Codeforces Round 889 (Div. Possible paths for the queries with "YES" answers are: The problem statement has recently been changed. Please someone guide. Now, Hanh performs $$$q$$$ operations, each is either of the following types: Since Hanh is good at biology but not math, he needs your help on these operations. Is v necessary? Problem link: Codeforces. My code is supposed to work in $$$O(n log n)$$$ as you see it. You have a rooted tree consisting of n vertices. With pa[17][100001], two consecutive accesses lead to a cache miss each time since the accessed memory locations are 100001 * sizeof(int) bytes apart. Is it possible to do that using the technique mentioned in the post? If $$$r = 4$$$, the values of vertices $$$1$$$, $$$2$$$, $$$3$$$ and $$$5$$$ get increased. The second query is $$$[2, 4, 6]$$$. GitHub, DP on Trees: Appleman and Tree | Codeforces | Rated 2000 - YouTube, Binary Tree Cameras | Leetcode | DP on Trees - YouTube, Binary lifting: Dynamic Programming on Trees - YouTube, Dynamic Programming on Trees - Codeforces. It seems like that many operations should be too slow for 4 seconds no matter how basic and cache-friendly they are. The only programming contests Web 2.0 platform. It is supported only ICPC mode for virtual contests. Then vertices $$$[3, 9, 10]$$$ belong to the path from $$$1$$$ to $$$10$$$ and the vertex $$$8$$$ has distance $$$1$$$ to the vertex $$$7$$$ which also belongs to this path. The essence of this tree decomposition is to split the tree into several paths so that we can reach the root vertex from any v by traversing at most log n paths. If you've seen these problems, a virtual contest is not for you - solve these problems in the archive. 1 + Div. Additionally, let $$$b$$$ be an array/Fenwick tree of size $$$2N$$$. Which problem is this a generalization of? NotImplemented +3 Heavy-Light Decomposition. The image below describes the tree (circles and solid lines) and the added edges for each query (dotted lines). 1-Trees and Queries CodeForces-1304E 1-Trees and Queries Codeforces 1304E 1-Trees and Queries (distance on trees + thinking) (translation direction) CodeForces-1304 E 1-Trees and queries Description Let there be a tree G of n vertices, with an arbitrary root. Next m lines contain the queries. The i-th line contains the numbers ai,bi (1ai,bin;aibi) the vertices connected by an edge of the tree. Problem - 1254D - Codeforces danielp - Topcoder Member Discuss this article in the forums. Can anybody tell me why :<. The $$$i$$$-th query consists of the set of $$$k_i$$$ distinct vertices $$$v_i[1], v_i[2], \dots, v_i[k_i]$$$. How to do fractional cascading on an iterative segment tree. It is supported only ICPC mode for virtual contests. Codeforces. 95 lines (78 sloc) 1.84 KB A tree with n vertices is an undirected connected graph with n 1 edges. That's a first time I see somebody have analysis on number of a cache misses better than "well, we go through all the data in right order so it should be fast(er)" but the interesting part: if I comment out sort part in the solution it still gets AC in 1.67 (and probably may be even a bit more faster if I delete all the code that actually calculates sizes which I am lazy to perform) so this time "by sorting we make paths closer in memory" analysis seems to be enough. The amount of information stored on $$$i$$$ is thus $$$a_{root[i]}$$$. Here are my solutions to the tree section of the problem-set. Your task is to process following types of queries: change the value of node s to x find the maximum value on the path between nodes a and b. If $$$r = 4$$$, the values of vertices $$$1$$$ and $$$3$$$ get increased. Let the time we enter node $$$i$$$ be $$$tin_i$$$ and the time we exit it be $$$tout_i$$$. Naive Approach is to find the answer for each query by simply traversing the array from index l till r and keep adding 1 to the count whenever the array element is greater than k. Algorithm: Initialize the array and its size Define a function countElements () to count the number of elements greater than k in subarray [l, r]: Help needed in Subtree Queries CSES - Codeforces Virtual contest is a way to take part in past contest, as close as possible to participation on time. You are given a rooted tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. A. Ian Visits Mary (800) B. If you're familiar with range updates and point queries with Fenwick trees, you'll know that if we want to increase the range $$$[A, B]$$$ by $$$X$$$ in an array/Fenwick tree $$$BIT$$$, then we increase $$$BIT[A]$$$ by $$$X$$$ and decrease $$$BIT[B + 1]$$$ by $$$X$$$. Each query is described by two integers vj,kj. For example, if we wanted to add $$$X$$$ to the subtree of $$$a_i$$$ in $$$O(\log N)$$$ time? If you only update tin[i] instead of both tin[i] and tout[i], you can get the subtree sum by querying the range [tin[i], tout[i]]. The only programming contests Web 2.0 platform, Editorial of Codeforces Round 889 (Div. It is supported only ICPC mode for virtual contests. I found it so simple and potentially usable that it deserves a post in my opinion. It is guaranteed that these $$$n - 1$$$ edges form a tree. Nice Tutorial.Hope I have learnt something new and interesting. The problem statement has recently been changed. Cannot retrieve contributors at this time. The Fox and the Complete Tree Traversal (2400) F. Misha and Apples (2800) 15. One more problem for this trick: http://codeforces.com/contest/925/problem/E (1.1s AC with 5s TL), The only programming contests Web 2.0 platform, http://codeforces.com/contest/925/problem/E, Editorial of Codeforces Round 889 (Div. As for HLD, in each path from a vertex to a vertex, we have here a O(logn) different subpaths, and each subpath is a consequtive segment in memory. Since Gildong was bored of solving too many tree problems, he wanted to see if similar techniques in trees can be used in 1-trees as well. Then the vertex $$$4$$$ has distance $$$1$$$ to the vertex $$$1$$$ which belongs to this path and the vertex $$$6$$$ has distance $$$1$$$ to the vertex $$$2$$$ which belongs to this path. Process $$$M$$$ of the following queries online: $$$N \leq 10^5$$$ and $$$M \leq 5 \cdot 10^5$$$. This gives us a way to find the amount of information on the merged component, but we still need a way to set each node in the component to have that amount of information. EDIT: didn't read the problem statement carefully enough, my bad. Problem link: Here is a link to my solution: The complexity is around O(q*log(n)) for all the print queries. It seems that the intended time complexity is $$$O(n\sqrt{n}\log{n})$$$, but I heard that it required efforts to get AC with this solution. Recently, I've prepaired $$$O(n^2)$$$ solution that used slow sort on array of $$$10^5$$$ ints and should get TLE. Codeforces/E_Tree_Queries.cpp at master - GitHub Seems like a different kind of problem (since you're updating paths rather than points). Example: 80876049 (here the maximum is required instead of the sum, but the idea is identical) rm[u][k] = max(rm[u][k - 1], rm[parent[u][k - 1]][k - 1]); calculates the maximum in a range of length $$$2^k$$$.