|
|
| Show all threads Hide all threads Show all messages Hide all messages | | Any hints? | Zergatul | 2119. Tree Hull | 4 Mar 2021 05:52 | 3 | My thoughts for now:
- Generate list of parents for every node, as well as weight sum (2nd parent, 4th parent, 8th parent and so on). This will allow to calculate weight sum between two nodes in O(log N)
- Implement LCA (better with O(1) time?)
- Store root of subtree in variable
- When new node comes, find LCA(new node, subtree root). 2 variants here:
1) LCA = new node (need to add sum of weights from new subtree root to previous subtree root)
2) LCA = existing subtree root. What to do here?
- When we remove node? Sort v_i by depth-first order.
d[v_i] is the sum of weights from the root to v_i
The answer, when there are n nodes, is:
sum_{i=1}^{n} d[v_i] - d[LCA(v_i, v_{i+1})]; where v_{n+1}:=v_1
Implement these operations using std::set with a custom comparator that orders vertices using depth-first order.
The proof of the formula is left to the reader as an exercise. WOW, that's really smart. Thank you | | Test for WA6 | Yury_Semenov | 2119. Tree Hull | 3 Jul 2020 17:43 | 1 | 5
1 2 1
2 3 1
3 4 1
4 5 1
7
+ 1
+ 3
+ 5
- 3
+ 4
- 1
- 5
ans:
0
2
4
4
4
1
0 | | WA 5, Help | Toshpulatov (MSU Tashkent) | 2119. Tree Hull | 11 Jan 2020 12:15 | 2 | WA 5, Help Toshpulatov (MSU Tashkent) 11 Jan 2020 02:07 TEST
10
1 7 1
1 8 1
1 2 1
7 10 1
7 9 1
9 3 1
8 4 1
2 5 1
5 6 1
6
+ 10
+ 1
+ 2
+ 8
+ 3
+ 6
ans = 8 |
|
|
|
