Simple And

Subtask 1: 1 ≤ N, Q ≤ 104

এই সাবটাস্কের জন্য, আমাদের কেবল ডিএফএস এর সহজ ধারণা প্রয়োজন। প্রথমে রুট থেকে, আমাদের একটি ডিএফএস চালানো উচিত যা প্রতিটি নোডের প্যারেন্ট নির্ধারণ করে। তারপরে প্রতিটি প্রশ্নের জন্য (u, k) আমাদের নোড u থেকে অন্য একটি ডিএফএস করা উচিত যা এর সাবট্রির k গভীরতায় যায় এবং বিটওয়াইস অ্যান্ড গণনা করে।

Subtask 2: k ≤ 1

পূর্ববর্তী সাবটাস্ক মত, প্রথমে রুট থেকে, আমাদের একটি ডিএফএস করা উচিত যা প্রতিটি নোডের প্যারেন্ট নির্ধারণ করে। যদি k = 0 হয় তবে উত্তর হবে নোডে উপস্থিত নম্বর । যদি k = 1 হয় তবে আমাদের কেবল নোড u এর সংলগ্ন অ্যাডজেসেন্সি লিস্ট দেখতে হবে এবং এটির প্যারেন্ট নোড ব্যতীত প্রতিটি নোডের মানের বিটওয়াইস অ্যান্ড গণনা করতে হবে। পূর্বে গণনা করা উত্তরগুলি পুনরায় গণনা এড়াতে আমাদের সংরক্ষণের প্রয়োজন হতে পারে। অন্যথায়, এটি TLE দিতে পারে।

Subtask 3:

মূল সাবটাস্কের জন্য, আমরা ডিএসইউ অন ট্রি নামে একটি ধারণা ব্যবহার করতে পারি।

প্রথমত প্রতিটি নোড v এর জন্য এই নোডের সাথে সম্পর্কিত সমস্ত প্রশ্নের সংরক্ষণ করি । তারপরে প্রতিটি নোডের জন্য, যা এর সাবট্রির রুট, একটি ডিএফএস চালাই । ডিএফএসের প্যারামিটার হ'ল নোড v এবং map<int,int>mp। এই মাপে v এর সাবট্রির প্রত্যেক গভীরতা i এর জন্যে mp[i] = সকল নোডের bitwise অ্যান্ড ভালু যাদের গভীরতা i.

এই map সহজভাবে গণনা করা যেতে পারে। v এর সমস্ত চিলড্রেন বিবেচনা কর এবং তাদের জন্য এমন map গণনা কর । স্পষ্টতই, আমাদের মাপ mp এর চিলড্রেন এর মধ্যে যার আকার সর্বাধিক তার আকারের হবে। তারপরে প্রতিটি চিলড্রেনএর মাপ বিবেচনা করি এবং সেগুলিকে একত্রিত করি । অবশ্যই, আমরা একটি বৃহত্তর মাপের সাথে একটি ছোট মাপ একীভূত করব। এর পরে, তোমার কাছে বর্তমান নোডের সমস্ত প্রশ্নের উত্তর দেওয়ার জন্যে প্রস্তুত । উত্তর হবে -1 যদি v এর গভীরতা k এ কোন চিলড্রেন না থাকে।