এখানে আমরা একটি সমস্যা দেখব, এই সমস্যায় একটি ট্রির এজ এবং একটি সম S দেওয়া আছে। টাস্ক হলো বাকি সব এজে ওয়েইট অ্যাসাইন করা যাতে ওয়েইট অনুযায়ী লংগেস্ট পাথ মিনিমাইজ হয়। অ্যাসাইন করা ওয়েইটগুলোর যোগফল 'S'-এর সমান হবে।
অ্যাপ্রোচটি সহজ। একটি ট্রির প্রোপার্টি যে একটি পাথে সর্বোচ্চ দুটি লিফ নোড থাকতে পারে। সেটি সমাধান পেতে ব্যবহার করা হবে। তাই যদি আমরা শুধু লিফ নোডগুলোকে কানেক্ট করা এজগুলোর ওয়েইট অ্যাসাইন করি, এবং অন্য এজগুলোর ০ অ্যাসাইন করি। তাহলে প্রতিটি এজ যা লিফ নোডের সাথে কানেক্টেড সেটিকে নিচের মতো অ্যাসাইন করা হবে
যেহেতু একটি পাথে সর্বোচ্চ দুটি লিফ নোড থাকতে পারে, তাই লংগেস্ট পাথ হবে
উদাহরণ
#include<iostream> #include<vector> using namespace std; void insertEdge(int u, int v, vector<int> adj[]) { adj[u].push_back(v); adj[v].push_back(u); } long double pathLength(vector<int> adj[], int sum, int n) { int count = 0; for (int i = 1; i <= n; i++) { if (adj[i].size() == 1) count++; } long double ans = 2.0 * (long double)(sum / (long double)(count)); return ans; } int main() { int n = 6; vector<int> adj[n + 1]; insertEdge(1, 2, adj); insertEdge(2, 3, adj); insertEdge(2, 4, adj); insertEdge(4, 5, adj); insertEdge(4, 6, adj); int sum = 1; cout << pathLength(adj, sum, n); }
আউটপুট
0.5
