Limits 1s, 256 MB

গাছে গাছে লাফানো মো জঙ্গলে একটি অসাধারণ গাছের সন্ধান পেয়েছে। সে গাছটিকে অনেক ভালোবেসে ফেলেছে। অল্প কিছুক্ষণের মধ্যেই সে এক ডাল থেকে অন্য ডালে অনেকবার লাফ দিয়ে ফেলেছে। বেশ পরে, লাফ দিতে দিতে বিরক্ত এবং অলস হয়ে সে ভাবতে শুরু করেছে, গাছের একটি নোড থেকে অন্য নোডে যেতে সর্বনিম্ন কত সময় লাগবে।

বস্তুত, একটা গাছ (বা ট্রি) হচ্ছে একটি কানেক্টেড গ্রাফ যার এজ-গুলো বাইডিরেকশনাল (বা দুইদিক দিয়েই আসা যাওয়া করা যায়) এবং যেকোন দুইটি নোডের মাঝে একটিমাত্র পথ আছে। মো যে ট্রি-টি খুঁজে পেয়েছে তাতে ঠিক $N$ টি নোড আছে এবং সেটার রুট (বা মূল) হচ্ছে 1। প্রত্যেক নোড $i$ এর রঙ $c_i$। নোড $u$ থেকে $v$ তে যেতে মো এর $d$ সেকেন্ড সময় লাগে যদি কি না $u, ~v$ অ্যাডজাসেন্ট হয়। আবার, মো $u$ থেকে $v$ তে লাফ দিয়ে যেতে পারে যদি ঐ দুটি নোডের রঙ একই হয় অর্থাৎ $c_u = c_v$। এই ধরণের লাফ দিতে তার $f_{c_u}$ সেকেন্ড সময় লাগে।

দুটি নোড $s$ এবং $t$ এর জন্য, বের করো $s$ থেকে $t$ তে যেতে সর্বনিম্ন কত সময় লাগে।

Input

ইনপুটের প্রথম লাইনে একটি ইন্টেজার থাকবে $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$.

Output

প্রতি টেস্টকেসের জন্য এক লাইনে প্রিন্ট করো $s$ থেকে $t$ তে যেতে সর্বনিম্ন কত সময় লাগে।

Sample

InputOutput
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() ইত্যাদি)

Submit

Login to submit.

Statistics

56% Solution Ratio
JONTRONAEarliest, Mar '20
Liad_HossainFastest, 0.3s
developer.spyderLightest, 15 MB
omar24Shortest, 1350B
Toph uses cookies. By continuing you agree to our Cookie Policy.