I_love_Vovuh_s_cat's blog

By I_love_Vovuh_s_cat, history, 5 years ago, In English

Given a tree with n nodes, rooted at 1. You have q offline queries with the form of ui, vi and xi. You have to add xi to every node in the simple path from ui to vi. It is guaranteed than ui is an ancestor of vi. Then you have to print out the values of all the nodes. The limit is... well, too large for O(n^2). Could anyone give me an approach to this problem?

Full text and comments »