Contribution Technique on Trees ft. CF2007E : Iris and the Tree
HTML-код
- Опубликовано: 9 ноя 2024
- Read this blog after watching the video : cfstep.com/tra...
Code, Slides, Practice Contest cfstep.com/cod...
Editorial for Problem E. Iris and the Tree from Codeforces Round 969 (Div. 2) and B. Iris and the Tree from Codeforces Round 969 (Div. 1)
CF2007E
CF2006B
Contribution Technique
Tree DP
Optimization
Codeforces
Lowest Common Ancestor (LCA)
Sum of pairwise distance between nodes in a tree
Great explanation, the amount of effort you put in for the video and the website is commendable!!
Thank you.
Was able to solve the weighted part completey myself after fully understanding contribution technique ....great video man..please keep uploading..
Bro i really liked your approach for problem solving please continue this series , very help full for competitive coders specially for higher ones .
Answer to last question:
For each edge (i, par[i]) it's contribution will be
(subtree(i) * (n - subtree(i))).
Do add this much for all edges to answer. Multiply weight of the edge for weighted graph.
Yep, that's correct.
02:22, i guess at here in special dfs tree, for the current node x, if it is a leaf node, dis(x,x+ 1) would not be 1.. to find x + 1, we can keep going to the parent until we find a parent with sub_max_node[parent] > x.. great explanation man..
understood 👍🏻♥️
Helpfull
Thanks. You have some good content on your channel as well. Keep it up!
@@cfstepofficial Thank You
I think some variables are not required.
unlocked_sum and locked_sum are not required only one variable sum will be sufficient.
Below assigned[v]+=w only do sum+=w and remove unblocked_sum and locked_sum from everywhere.
At time of events your answer would be ans=sum+unlocked_count*remain
Why?
Because see brute force you will notice you need sum of all node's assigned[i] value and assigned [i] value is just some of w's.
So, the "sum" is doing the same thing. Keep everything else same.
Please correct me if i am wrong anywhere.
Btw your explanations are too good keep it up.
Fair enough.