সব সময়ের মত এলিস এবং বব এখনও একটি গেম খেলতেসে। এই গেমটিতে এলিস ববকে একটি ট্রি দিয়েছে এবং গেম টির নিম্নরূপ বর্ণনা দিয়েছে :
- ট্রি এর প্রতিটি নোডে কিছু পয়েন্ট আছে।
- বব যে কোন নোড থেকে গেম শুরু করে যে কোন নোডে গেম শেষ করতে পারে।
- বব যখন কোনও নোডে যায় তখন ঐ নোডের সব পয়েন্ট ববের স্কোরের সাথে যোগ হয়ে যায় এবং ঐ নোড এর পয়েন্ট শূন্য হয়ে যায়।
- প্রতিটি চালে, সমান সম্ভাব্যতায় বব যে নোড এ আছে তার পার্শ্ববর্তী যে সকল নোড এর পয়েন্ট শূন্য থেকে বেশি সে সকল নোডে যেতে পারে অথবা বর্তমান নোডে গেমটি শেষ করতে পারে।
- বব যখন গেম টি শেষ করবে তখন ববের স্কোর যদি দুই দ্বারা বিভাজ্য হয় তবে সে বিজয়ী হবে অন্যথায় অ্যালিস বিজয়ী হবে।
এখন এলিস এই খেলায় তার জয়ের সম্ভাবনা কত তা বব এর কাছ থেকে জানতে চায়। যেহেতু বব এখন এই সমস্যার নাম "Maze Runner" কেন এটি নিয়ে ভাবতে ব্যস্ত রয়েছে, তাই এই সমস্যাটি সমাধান করার জন্য তাঁর আপনার সহায়তা প্রয়োজন।
Input
ইনপুটটি একটি পূর্ণসংখ্যা T দিয়ে শুরু হয় যা প্রব্লেম এর টেস্ট কেসের সংখ্যা বোঝায়। প্রতিটি টেস্ট কেসের প্রথম লাইনে একটি পূর্ণসংখ্যা N রয়েছে যা ট্রি এর নোডের সংখ্যা নির্দেশ করে। পরবর্তী লাইনে N টি পূর্ণসংখ্যা রয়েছে যা প্রতিটি নোডের পয়েন্ট নির্দেশ করে। পরবর্তী N-1 টি লাইনে, দুটি করে পূর্ণসংখ্যা U এবং V দেওয়া আছে যা ট্রি এর U এবং V নোড এর মধ্যে একটি এজ নির্দেশ করে।
1 ≤ T ≤ 10
1 ≤ N ≤ 105
1 ≤ পয়েন্ট ≤ 1000
1 ≤ U, V <= N এবং U ≠ V
Output
প্রতিটি টেস্ট কেস এর আউটপুট একটি দশমিক যুক্ত সংখ্যা হবে যা সমস্যাটিতে জিজ্ঞাসা করা সম্ভাবনার মান নির্দেশ করেবে। আপনার উত্তর এবং স্ট্যান্ডার্ড উত্তরের মধ্যে পার্থক্য যদি 10-6 এর বেশি না হয় তবে তা সঠিক হিসাবে গ্রহণযোগ্য হবে।
Sample
| Input | Output |
|---|---|
2 3 2 2 2 1 2 1 3 6 2 1 1 1 1 1 1 2 2 3 3 5 3 6 2 4 | 0.0000000000 0.5714285714 |
গ্রাফ থিউরিতে, ট্রি হচ্ছে একটি আনডিরেক্টেড গ্রাফ, যেখানে গ্রাফের যে কোন দুটি নোডের মধ্যে একটি ও কেবলমাত্র একটি পথই বিদ্যমান।
