Appleman and Tree - CF 461B
প্রবলেমটা মূলত ডিপি অন ট্রি প্রবলেম। এখানে একটা ট্রি দেয়া আছে , যার প্রত্যেকটা নোড হয় ব্লাক অথবা হোয়াইট। এখন লক্ষ্য করি, ট্রির যেকোনো একটি এজ যদি আমরা ডিলিট করি তাহলে দুইটি নতুন ট্রি পাবো । দুটি এজ ডিলিট করলে আমরা তিনটি নতুন ট্রি পাবো। অর্থাৎ , ক সংখ্যক এজ ডিলিট করলে আমরা ক+১ টি নতুন ট্রি/ কম্পোনেন্ট পাবো। কিন্তু আমাদের এমন ভাবে এজগুলো ডিলিট করতে হবে যাতে ডিলিট করার পর প্রত্যেকটা কম্পোনেন্ট এ একটি মাত্র ব্লাক নোড থাকে। বলতে হবে এমন কত উপায়ে ট্রি এর এজগুলোকে ডিলিট করা যাবে। কিছু বিষয় লক্ষ্য করা যাক। যদি ট্রি তে সবগুলো নোড ই ব্লাক হয় তাহলে এক উপায়েই তাদের এজগুলো ডিলিট করা যায় । যদি ট্রি এর রুট নোড ব্লাক হয় এবং চাইল্ড নোড হোয়াইট হয়, তাহলে তার চাইল্ড নোডের সাথে থাকা এজটিকে আমরা ডিলিট করতেও পারি নাও করতে পারি। রুট নোড হোয়াইট আর চাইল্ড নোড ব্লাক হলেও একই বিষয়। হোয়াইট নোড এর চাইল্ড হোয়াইট নোড হলেও তাই । সুতরাং , আমাদের যদি জানা থাকে চাইল্ড নোড গুলোর প্রত্যেক্টার জন্য কত উপায়ে এজ স্প্লিট করা যায় আমরা রুট নোডের জন্যও কম্বিনেশন বের করে ফেলতে পারি। এখানে , খেয়া...