|
|
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 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 What is 5 test ? 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 |
|
|
