anirbang749's blog

will the following piece of code work in O(nlog(n)) time ?

By anirbang749, history, 14 hours ago, In English

Find the number of unique values in the subtree of a node .

#include <bits/stdc++.h>
using namespace std;

int par[100100];
int val[100100];
vector<int> g[100100];
set<int> uunique[100100]; 


void dfs(int node, int parent) {
    par[node] = parent;
    for (auto neigh : g[node]) {
        if (neigh != parent) {
            dfs(neigh, node);
        }
    }
    for(auto v : uunique[node]){
        uunique[par[node]].insert(v);
    }
}

int main() {
    int n;
    cin >> n;
    int m = n - 1;

    while (m--) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        cin >> val[i];
        uunique[i].insert(val[i]); 
    }

    dfs(1, 0); 

    for (int node = 1; node <= n; node++) {
        cout << "Number of unique values in the subtree of " << node
             << " are " << (int)uunique[node].size() << '\n';
    }

    return 0;
}
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
14 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

This code seems to be for problem CSES — Distinct Colors.

If you did small to large, the complexity would be $$$O(n \cdot \log{(n)}^2)$$$, but this code is $$$O(n^2)$$$

→ Reply
  • »
    »
    14 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's $$$O(n^2 \cdot log(n))$$$ actually. It'll be $$$O(n^2)$$$ if use std::unordered_set instead of std::set

    → Reply
    • »
      »
      »
      14 hours ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks for the correction

      → Reply
    • »
      »
      »
      13 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please provide me the template code for this

      → Reply
  • »
    »
    13 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    #include <bits/stdc++.h>
using namespace std;

int par[100100];
int val[100100];
vector<int> g[100100];
set<int> uunique[100100]; // Directly store sets for each node

void dfs(int node, int parent) {
    par[node] = parent;

    // Insert the node's value into its own set
    uunique[node].insert(val[node]);

    for (auto neigh : g[node]) {
        if (neigh != parent) {
            dfs(neigh, node);

            // Small-to-large merging: merge smaller set into the larger one
            if (uunique[neigh].size() > uunique[node].size()) {
                swap(uunique[node], uunique[neigh]);
            }
            uunique[node].insert(uunique[neigh].begin(), uunique[neigh].end());
        }
    }
}

int main() {
    int n;
    cin >> n;
    int m = n - 1;

    // Read tree edges
    while (m--) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    // Read node values
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }

    // Run DFS from the root (assuming node 1 is the root)
    dfs(1, 0);

    // Output the size of the unique set for each node
    for (int node = 1; node <= n; node++) {
        cout << "Number of unique values in the subtree of " << node
             << " are " << uunique[node].size() << '\n';
    }

    return 0;
}
    → Reply
    • »
      »
      »
      12 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You need to store the answer for every node after finishing, here what I would modify:

      Code
      → Reply