এখানে আমরা একটি সমস্যা দেখব, এই সমস্যাটিতে একটি গাছের একটি প্রান্ত এবং একটি যোগফল S দেওয়া হয়েছে। কাজটি হল অন্যান্য সমস্ত ওজনের জন্য ওজন নির্ধারণ করা, যেমন ওজনের দিক থেকে দীর্ঘতম পথটি ছোট করা হয়। এটির জন্য নির্ধারিত ওজনের যোগফল 'S' এর সমান।
পদ্ধতি সহজ. একটি গাছের বৈশিষ্ট্য যে একটি পথের মধ্যে সর্বাধিক দুটি পাতার নোড থাকতে পারে৷ যে সমাধান পেতে ব্যবহার করা হবে. তাই যদি আমরা লিফ নোডগুলির সাথে সংযোগকারী প্রান্তগুলির ওজন নির্ধারণ করি এবং অন্যান্য প্রান্তগুলিকে 0 তে বরাদ্দ করি৷ তাহলে প্রতিটি প্রান্ত যা লিফ নোডগুলির সাথে সংযোগ করছে তা হিসাবে বরাদ্দ করা হবে
যেহেতু একটি পাথে সর্বাধিক দুটি লিফ নোড থাকতে পারে, তাই দীর্ঘতম পথটি হবে
উদাহরণ
#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
