Yet Another XOR Tree Problem

সাবটাস্ক 1:
যে কোনও ব্রুটফোর্স সলিউশনেই হয়ে যাওয়া উচিত।

সাবটাস্ক 2:
প্রতিটি $query(U, V)$ তে, নোড $U$ কে ট্রির রুট নোড হিসাবে বিবেচনা কর । নোড $U$ থেকে একটি বিএফএস/ডিএফএস চালাও এবং নোড $U$ এবং নোড $V$ এর মধ্যবর্তী সিম্পল পথে অবস্থিত নোডগুলির ট্র্যাক রাখ । এটা তুমি একটি $par[]$ এ্যারে ম্যানেজ করার মাধ্যমে করতে পারবে, যেখানে $par[i]=$ নোড $i$ এর ইমিডিয়েট প্যারেন্ট। বিএফএস/ডিএফএস চালানোর সময় সব নোড $U$-র জন্য $F(U,i)$-ও ক্যালকুলেট করে রাখতে হবে । বাকিটা নিজে নিজে চেষ্টা কর ।

সাবটাস্ক 3:
তুমি যদি Trie ডাটা স্ট্রাকচার দিয়ে ম্যাক্সিমাম $K\oplus A_i$ বের করার সাথে পরিচিত না থাক, তাহলে প্রথমে এই লিংকের লেখাটি পড়ে নাও ।

ট্রির যেকোনো একটি নোডকে রুট নোড হিসেবে ধরা যাক । নিচের উদাহরণে নোড $1$ কে রুট নোড ধরা হয়েছেঃ

এজের ওয়েটগুলো লাল রঙে লেখা হয়েছে । এখানে, $F(1, 4) = 9\oplus 6, \space F(1, 3) = 9\oplus 5$ । তাহলে, $F(1,4) \oplus F(1,3) = 9\oplus 6\oplus 9\oplus 5 = 6 \oplus 5 = 3$, যা আসলে $F(4, 3)$ এর ভ্যালু । অর্থাৎ, আমরা $F(U, V)$ কে $F(root, U) \oplus F(root, V)$ হিসেবে লিখতে পারি ।

ধরা যাক, নোড $U$ এবং নোড $V$ এর Lowest Common Ancestor (LCA) হচ্ছে নোড $L$ । এখন ক্যুয়েরীতে, আমরা $query(U, V)$ কে দুইটি আলাদা ক্যুয়েরীতে ভাগ করতে পারি: $query(L, U, F(root, U))$ এবং $query(L, V, F(root, U))$, যেখানে $query(x, u, k)$ বোঝায় $k\oplus F(root, i)$ এর ম্যাক্সিমাম ভ্যালু, যাতে নোড $i$, নোড $x$ এবং নোড $u$ কে সংযোগকারী সিম্পল পথের উপর থাকে এবং নোড $x$  হচ্ছে নোড $u$ এর কোনো এনসেস্টর বা নোড $u$ । এই দুটি আলাদা ক্যুয়েরীর ম্যাক্সিমাম হচ্ছে আমাদের আসল ক্যুয়েরীর উত্তর ।

$query(x, u, k)$-র উত্তর বের করতে, আমাদের প্রথমে সব নোড $u$ এর জন্য $F(root, u)$-র ভ্যালু প্রিক্যালক্যুলেট করে রাখতে হবে । এরপর $F(root, j)$-র ভ্যালুগুলো দিয়ে আমরা একটি Trie বিল্ড করতে পারি, যেখানে $j$ হচ্ছে নোড $u$ এর কোনো এনসেস্টর বা নোড $u$ । তাহলে এটি এডিটোরিয়ালের (সাবটাস্ক 3) শুরুতে বলা সাধারণ Trie প্রবলেমের মত হয়ে যায় । তবে এমন কোনো Trie নোডে সার্চ করা যাবে না যেটা শুধুমাত্র নোড $x$ এর এনসেস্টরের ভ্যালু দিয়ে তৈরি । এটা নিশ্চিত করতে আমরা Trie নোডে ম্যাক্সিমাম ডিএফএস ডিসকভারি টাইমের ট্র্যাক রাখতে পারি অথবা এই ধরণের অন্য কিছু করতে পারি ।

যেহেতু সব নোড $u$ এর জন্য $F(root, j)$-র ভ্যালুগুলো দিয়ে Trie বিল্ড করতে অনেক বেশি মেমোরির প্রয়োজন, তাই আমাদের Persistent Trie ডাটা স্ট্রাকচার ব্যবহার করতে হবে ।

এই প্রবলেম সাধারণ Trie ব্যবহার করেও সলভ করা সম্ভব প্রথমে সব ক্যুয়েরী স্টোর করে রেখে পরে উত্তর প্রিন্ট করে (অফলাইন ক্যুয়েরী) । এই এপ্রোচেও উপরের কনসেপ্ট অনেক সাহায্য করবে ।

সেটারের সলিউশনঃ https://pastebin.com/Xdn7SrDD