সমস্যা
একটি রুটেড ট্রি দেওয়া যেখানে প্রতিটি নোডের একটি কালার আছে। কুয়েরি: একটি নোড দেওয়া হলে তার সাবট্রিতে কতটি ডISTINCT কালার আছে।
অ্যালগরিদম: অয়লার টুর + BIT (Fenwick Tree)
- DFS করে অয়লার টুর অর্ডার (
tin,tout) বানান। সাবট্রি = কন্টিগুয়াস রেঞ্জ[tin[u], tout[u]]। - ফ্ল্যাট অ্যারেতে প্রতিটি কালারের সর্বশেষ অকারেন্সে BIT-এ ১ রাখুন।
- কুয়েরি সর্ট করুন
tinঅনুযায়ী। - সweep line: লেফ্ট বাউন্ডারি বাড়াতে গিয়ে পুরনো অকারেন্স রিমুভ করুন, নতুন অকারেন্স অ্যাড করুন।
- রেঞ্জ সম = BIT কুয়েরি(
tout[u]) - BIT কুয়েরি(tin[u]-1)।
C++ কোড (সংক্ষিপ্ত)
#include <bits/stdc++.h>
#define MAXC 1000005
#define MAXN 100005
using namespace std;
vector<int> tree[MAXN], colorPos[MAXC];
int bit[MAXN], tin[MAXN], tout[MAXN], flat[2*MAXN], timer=0;
bool vis[MAXN];
vector<pair<pair<int,int>,int>> queries;
int ans[MAXN], iter[MAXC];
void update(int idx, int val) {
for (; idx0; idx-=idx&-idx) res+=bit[idx]; return res;
}
void dfs(int v, int color[]) {
vis[v]=1; tin[v]=++timer; flat[timer]=color[v];
for(int to: tree[v]) if(!vis[to]) dfs(to,color);
tout[v]=++timer; flat[timer]=color[v];
}
int main() {
// ইনপুট প্রসেস, dfs(1), কুয়েরি সর্ট, sweep, আউটপুট
}
আউটপুট (নমুনা)
All distinct colours in the given tree: 1 All distinct colours in the given tree: 2
