Rerooting DP Explained | AtCoder DP Contest V – Subtree | DP on Trees in C++

Описание: 🌳 𝐑𝐞𝐫𝐨𝐨𝐭𝐢𝐧𝐠 𝐃𝐏 – 𝐀𝐭𝐂𝐨𝐝𝐞𝐫 𝐃𝐏 𝐂𝐨𝐧𝐭𝐞𝐬𝐭 𝐕: 𝐒𝐮𝐛𝐭𝐫𝐞𝐞 | 𝐃𝐲𝐧𝐚𝐦𝐢𝐜 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 𝐨𝐧 𝐓𝐫𝐞𝐞𝐬 (𝐅𝐮𝐥𝐥 𝐈𝐧𝐭𝐮𝐢𝐭𝐢𝐨𝐧)⁣
⁣
In this video, we solve the “Subtree” problem (V – Subtree) from the AtCoder Educational DP Contest and use it to build a deep understanding of Rerooting DP on Trees, from basic intuition to advanced implementation.⁣
⁣
We start from:⁣
⁣
simple tree DP (rooted at 1)⁣
then move to⁣
full rerooting DP, where we compute the answer for every node as root by “reusing” information and propagating DP values efficiently.⁣
⁣
If you’ve ever been confused by rerooting DP, this video is meant to make it click permanently. 🔁🌳⁣
⁣
💡 𝐖𝐡𝐚𝐭 𝐘𝐨𝐮’𝐥𝐥 𝐋𝐞𝐚𝐫𝐧⁣
⁣
What Rerooting DP is and why we need it⁣
Difference between:⁣
normal tree DP (single root) and⁣
rerooting DP (answer for all roots)⁣
⁣
How to:⁣
compute DP values downwards (subtree DP)⁣
then reroot / re-use them to get answers for every vertex⁣
⁣
How the “black vertices must form a connected component” condition turns into a nice DP formulation⁣
⁣
Full C++ implementation with explanation of:⁣
DP states⁣
transitions⁣
modulo operations⁣
⁣
🧩 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐈𝐧𝐟𝐨⁣
⁣
Problem: AtCoder Educational DP Contest – V: Subtree⁣
Topic: Rerooting DP, Tree DP, Graph DP⁣
Difficulty: Advanced (great for strong DP / CP learners)⁣
Language: C++⁣
⁣
🧠 𝐓𝐨𝐩𝐢𝐜𝐬 𝐂𝐨𝐯𝐞𝐫𝐞𝐝⁣
⁣
Rerooting DP (Re-rooting Technique on Trees)⁣
DP on Trees (upward & downward passes)⁣
Subtree DP + DP on the “complement” of subtree⁣
Modular counting on trees (answers modulo M)⁣
Typical patterns used for many AtCoder / Codeforces tree problems⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣This is part of my 𝐃𝐏 𝐨𝐧 𝐓𝐫𝐞𝐞𝐬 𝐚𝐧𝐝 𝐃𝐀𝐆𝐬 𝐒𝐞𝐫𝐢𝐞𝐬, where I cover smart and creative problems that teach you how to build solutions from logic — a key skill in competitive programming 🚀⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
💡 𝐓𝐡𝐢𝐬 𝐯𝐢𝐝𝐞𝐨 𝐰𝐢𝐥𝐥 𝐡𝐞𝐥𝐩 𝐲𝐨𝐮 𝐮𝐧𝐝𝐞𝐫𝐬𝐭𝐚𝐧𝐝 𝐡𝐨𝐰 𝐭𝐨 𝐭𝐡𝐢𝐧𝐤 𝐜𝐨𝐧𝐬𝐭𝐫𝐮𝐜𝐭𝐢𝐯𝐞𝐥𝐲, 𝐛𝐮𝐢𝐥𝐝 𝐬𝐨𝐥𝐮𝐭𝐢𝐨𝐧𝐬 𝐥𝐨𝐠𝐢𝐜𝐚𝐥𝐥𝐲, 𝐚𝐧𝐝 𝐬𝐭𝐫𝐞𝐧𝐠𝐭𝐡𝐞𝐧 𝐲𝐨𝐮𝐫 𝐩𝐫𝐨𝐛𝐥𝐞𝐦-𝐬𝐨𝐥𝐯𝐢𝐧𝐠 𝐦𝐢𝐧𝐝𝐬𝐞𝐭 — 𝐩𝐞𝐫𝐟𝐞𝐜𝐭 𝐟𝐨𝐫 𝐂𝐒𝐄𝐒, 𝐂𝐨𝐝𝐞𝐟𝐨𝐫𝐜𝐞𝐬, 𝐀𝐭𝐂𝐨𝐝𝐞𝐫, 𝐚𝐧𝐝 𝐈𝐂𝐏𝐂 𝐜𝐨𝐧𝐭𝐞𝐬𝐭𝐬.⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣
📘𝐍𝐨𝐭𝐞𝐬: ⁣⁣⁣⁣⁣⁣⁣⁣⁣
https://github.com/yash7xm/cp_notes/b...
⁣⁣⁣⁣⁣⁣⁣⁣⁣
𝐂𝐨𝐝𝐞: https://github.com/yash7xm/cp-topics/...
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
👉 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐋𝐢𝐧𝐤:⁣ https://atcoder.jp/contests/dp/tasks/...
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
🔗 𝐏𝐥𝐚𝐲𝐥𝐢𝐬𝐭:    • DP on Trees & DAGs | Dynamic Programming o...  
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣💡 𝐏𝐞𝐫𝐟𝐞𝐜𝐭 𝐟𝐨𝐫:⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
Competitive programmers⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
Data structure & algorithms learners⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
Coding interview prep⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
📌 Watch this till the end to fully understand the intuition, not just the code.⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
👉 Whether you’re a beginner or looking to strengthen your logical thinking, this course will help you 𝐭𝐡𝐢𝐧𝐤 𝐥𝐢𝐤𝐞 𝐚 𝐜𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐩𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐞𝐫 𝐚𝐧𝐝 𝐝𝐞𝐬𝐢𝐠𝐧 𝐜𝐨𝐧𝐬𝐭𝐫𝐮𝐜𝐭𝐢𝐯𝐞 𝐬𝐨𝐥𝐮𝐭𝐢𝐨𝐧𝐬 𝐜𝐨𝐧𝐟𝐢𝐝𝐞𝐧𝐭𝐥𝐲 𝐢𝐧 𝐜𝐨𝐧𝐭𝐞𝐬𝐭𝐬.⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
👋 𝐖𝐞𝐥𝐜𝐨𝐦𝐞 𝐭𝐨 𝐭𝐡𝐞 𝐜𝐡𝐚𝐧𝐧𝐞𝐥!⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
I create content on 𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠, 𝐃𝐚𝐭𝐚 𝐒𝐭𝐫𝐮𝐜𝐭𝐮𝐫𝐞𝐬 & 𝐀𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦𝐬 (𝐃𝐒𝐀), 𝐚𝐧𝐝 𝐓𝐞𝐜𝐡𝐧𝐢𝐜𝐚𝐥 𝐈𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐏𝐫𝐞𝐩𝐚𝐫𝐚𝐭𝐢𝐨𝐧.⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
If you find this video helpful, don’t forget to:⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
👍 Like the video⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
💬 Comment your doubts/questions (I reply to everyone!)⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
🔔 Subscribe and turn on notifications to never miss upcoming tutorials⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
📌 𝐂𝐨𝐧𝐧𝐞𝐜𝐭 𝐰𝐢𝐭𝐡 𝐦𝐞:⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
🐦 X: https://x.com/Yash_Poonia_⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣...
💼 LinkedIn:   / ⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣...  
💻 GitHub: https://github.com/yash7xm⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣...
🌐 Discord:   / discord  
⁣⁣⁣⁣⁣⁣⁣⁣
#RerootingDP #DPonTrees #AtCoder #DynamicProgramming #TreeDP #GraphDP #CompetitiveProgramming #DSA #Cplusplus #AlgorithmTutorial #AtCoderDP #DynamicProgrammingOnTrees #DSASeries #LearnDSA⁣
⁣