গাছে গাছে লাফানো মো জঙ্গলে একটি অসাধারণ গাছের সন্ধান পেয়েছে। সে গাছটিকে অনেক ভালোবেসে ফেলেছে। অল্প কিছুক্ষণের মধ্যেই সে এক ডাল থেকে অন্য ডালে অনেকবার লাফ দিয়ে ফেলেছে। বেশ পরে, লাফ দিতে দিতে বিরক্ত এবং অলস হয়ে সে ভাবতে শুরু করেছে, গাছের একটি নোড থেকে অন্য নোডে যেতে সর্বনিম্ন কত সময় লাগবে।
বস্তুত, একটা গাছ (বা ট্রি) হচ্ছে একটি কানেক্টেড গ্রাফ যার এজ-গুলো বাইডিরেকশনাল (বা দুইদিক দিয়েই আসা যাওয়া করা যায়) এবং যেকোন দুইটি নোডের মাঝে একটিমাত্র পথ আছে। মো যে ট্রি-টি খুঁজে পেয়েছে তাতে ঠিক $N$
টি নোড আছে এবং সেটার রুট (বা মূল) হচ্ছে 1। প্রত্যেক নোড $i$
এর রঙ $c_i$
। নোড $u$
থেকে $v$
তে যেতে মো এর $d$
সেকেন্ড সময় লাগে যদি কি না $u, ~v$
অ্যাডজাসেন্ট হয়। আবার, মো $u$
থেকে $v$
তে লাফ দিয়ে যেতে পারে যদি ঐ দুটি নোডের রঙ একই হয় অর্থাৎ $c_u = c_v$
। এই ধরণের লাফ দিতে তার $f_{c_u}$
সেকেন্ড সময় লাগে।
দুটি নোড $s$
এবং $t$
এর জন্য, বের করো $s$
থেকে $t$
তে যেতে সর্বনিম্ন কত সময় লাগে।
ইনপুটের প্রথম লাইনে একটি ইন্টেজার থাকবে $T$
।
$T$
টি টেস্টকেস থাকবে। প্রতি টেস্টকেসের জন্য ---
$N, ~d$
, যথাক্রমে মোট নোড সংখ্যা এবং অ্যাডজাসেন্ট নোডগুলার মাঝে যাতায়াত করার সময়। নোডগুলো $1$
থেকে $N$
পর্যন্ত নাম্বারিং করা।$N-1$
টি ইন্টেজার থাকবে, $i$
-তম টি নোড $i+1$
এর প্যারেন্ট।$N$
টি ইন্টেজার থাকবে, $i$
-তম টি নোড $i$
এর রঙ $c_i$
।$N$
টি ইন্টেজার থাকবে যার $i$
-তম টি নির্দেশ করবে $f_{c_i}$
। এটি নিশ্চিত যে যেকোন $i, ~j$
এর জন্য যদি $c_i = c_j$
হয় তাহলে $f_{c_i} = f_{c_j}$
হবে।$s$
এবং $t$
, শুরুর নোড এবং গন্তব্য নোড।সাবটাস্ক ১ (২০ পয়েন্ট):
$1 \leq T \leq 5$
,$2 \leq N \leq 10^3$
,$1 \leq c_i, s, t \leq N$
,$0 \leq d, f_{c_i} \leq 10^4$
.সাবটাস্ক ২ (৩০ পয়েন্ট):
$1 \leq T \leq 10$
,$2 \leq N \leq 10^5$
,$1 \leq c_i, s, t \leq N$
,$0 \leq d, f_{c_i} \leq 10^7$
,$d = f_{c_i}$
- যেকোন $c_i$
এর জন্য।সাবটাস্ক ৩ (৫০ পয়েন্ট):
$1 \leq T \leq 10$
,$2 \leq N \leq 10^5$
,$1 \leq c_i, s, t \leq N$
,$0 \leq d, f_{c_i} \leq 10^7$
.প্রতি টেস্টকেসের জন্য এক লাইনে প্রিন্ট করো $s$
থেকে $t$
তে যেতে সর্বনিম্ন কত সময় লাগে।
Input | Output |
---|---|
1 8 10 1 2 2 4 4 1 6 3 2 4 4 3 2 1 4 12 20 14 14 12 20 5 14 7 8 | 44 |
Mo walks 7-1 in d=10 seconds. 1-2 in another 10 seconds. Then he goes to 3 via 2-3 causing another 10 seconds. Then he jumps from vertex-3 to vertex-8 since they are the same color. This jump takes him 14 seconds. Total time: 44 seconds. |
ইনপুট ফাইল বেশ বড়। ফাস্টার ইনপুট-আউটপুট প্রোসেসিং ফাংশন বা স্ট্রিম ব্যবহার কর (যেমন সি বা সি++ এর জন্য scanf(), printf() ইত্যাদি)