Help Required CSES Distinct Colors

#	User	Rating
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

#	User	Contrib.
1	Qingyu	155
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	134
9	maroonrk	132
10	cry	130

Hello guys,

I was trying to solve Distinct Colors: link.

I did a naive solution which obviously led to TLE.

TLE

vector<VII> adj(2e5);
map<int, VII> col;
VII sub(2e5, 0);
VII ind(2e5, 0);
VII v(2e5);
int t = 1;
int dfs(int u,int p)
{
    for(auto it:adj[u])
    if(it!=p)
        sub[u] += dfs(it, u);
    
 
    ind[u] = t++;
    col[v[u]].pb(ind[u]);
    sub[u]++;
    return sub[u];
}
int main(int argc, char *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n;++i)
        cin >> v[i];
 
    for (int i = 0; i < n - 1;++i)
    {
        int x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
 
    dfs(1, -1);
    for (int i = 1; i <= n;++i)
    {
        int l = ind[i] - sub[i] + 1;
        int r = ind[i];
        int ans = 0;
        for(auto c:col)
        {
            auto lll = lower_bound(all(c.second), l);
            auto rr = upper_bound(all(c.second), r);
            if(rr-lll>=1)
                ans++;
        }
        cout << ans << ' ';
    }
    return 0;
}

I saw various solutions that use BIT. But I cant assimilate why BIT works here, what BIT represents here (for e.g. in case range sum query BIT keeps track of cummulative frequency.)

It would be great if someone tells some trick how to use BIT for various other purposes too.

Thanks!

Comments (11)

Show archived | Write comment?

LanceTheDragonTrainer

6 years ago, hide # |

It's simple. Simply transform your tree into an array by doing a pre-order traversal. Then, notice that a subtree corresponds to a subarray. Now, you just need to solve the problem of finding the number of distinct elements in a subarray (which is actually SPOJ DQUERY).

→ Reply

retr0coderxyz

6 years ago, hide # ^ |

← Rev. 2 →

Thanks buddy, I have done till subarray part. epitome of this question lies around finding distinct numbers within range ( which I have used map and binary search to check here). So I need help in that part.

There are several ways to solve the problem for the array version.

The most straightforward is to use Mo's algo.

Since you asked for fenwick tree solution specifically, I shall tell you something — it is not so straightforward (you need a clever trick).

Segment tree with a vector in each node provides you with a much more straightforward solution.

Can you elaborate on the segment tree part, Thanks — noob here :(

Hint: (Sweeping from left to right), for each color in your array, store the index of the next occurence of that color. If there is none, use infinity.

Actually, you can also solve this without flattening the tree. But that's a bit advanced for now...

tihsrah_1177

LanceTheDragonTrainer Can you please explain how we can solve this without flattening the tree

CoderAnshu

using dsu on trees (sack) ,You can take help from here : https://codeforces.me/blog/entry/44351

nishuz

You can solve with small to large merging.

Code

LanceTheDragonTrainer gave some valuable insights, but still its not enough for me to pick up. I honestly don't understand "(Sweeping from left to right), for each color in your array, store the index of the next occurence of that color. If there is none, use infinity." works or what to do after that. It will be great if anybody could explain me in a well detailed manner out of your busy time, I would be really grateful.

Thank you!

Everule

Notice that each distinct color will have only one index where the value of next_element is larger than your right end.

retr0coderxyz's blog