Блог

Я пытался решить вопрос о cses — Разные цвета, мое решение основано на книге «Справочник конкурентоспособного программиста» Антти Лааксонена номер страницы 170 (Объединение структур данных)

 #include<bits/stdc  .h>
using namespace std;
const int Mxn = 2e5;
unordered_set<int> adj[Mxn],mp[Mxn];
int c[Mxn],ans[Mxn],n;
 
void dfs(int u=0, int p = -1){
    for(auto v: adj[u]){
        if(v != p){
            dfs(v,u);
            if(mp[v].size() > mp[u].size())
                swap(mp[v],mp[u]);
            mp[u].insert(mp[v].begin(),mp[v].end());
        }
    }
    mp[u].insert(c[u]);
    ans[u] = mp[u].size();
}
 
int main(){
    cin>>n;
    for(int i=0;i<n;i  ) cin>>c[i];
    for(int i=1;i<n;i  ){
        int x,y; cin>>x>>y; x--,y--;
        adj[x].insert(y);
        adj[y].insert(x);
    }
    dfs();
    for(int i=0;i<n;i  ) cout<<ans[i]<<' ';
}
 

Что я хочу знать, так это то, что когда я меняю местами две карты в приведенном выше коде, используя

 if(mp[v].size() > mp[u].size())
    swap(mp[v],mp[u]);
 

Код принимается, но когда я не меняю местами эти карты, я получаю TLE, вот цитата из книги :

Объединение узлов может быть выполнено следующим образом: мы проходим через дочерние элементы s и в каждом дочернем элементе u объединяем d [s] и d[u] . Мы всегда копируем содержимое из d [u] в d [s] . Однако перед этим мы поменяем местами содержимое d [s] и d[u], если d[s] меньше, чем d [u] . При этом каждое значение копируется только O (log (n)) раз во время обхода дерева, что гарантирует эффективность алгоритма.

как замена карт в соответствии с их размером гарантирует, что каждый элемент будет скопирован не более O (log (N)) раз?

Если все цвета уникальны, то сложность копирования одной карты в другую будет O (N), верно? Это сделало бы общую сложность O (N ^ 2).

Я почти уверен, что этот алгоритм известен как «слияние малого и большого». Основная идея заключается в том, что каждая вершина будет объединена в большинстве log(N) случаев.

Во-первых, условие подкачки гарантирует, что меньший набор будет объединен с большим набором. Таким образом, каждый раз, когда какая-либо вершина v объединяется, новый набор, содержащий v , будет по крайней мере в два раза превышать размер исходного набора, содержащего v . Мы можем представить, что размер наборов, содержащихся v после каждого слияния, будет выглядеть примерно так: 1 -> 2 -> 4 -> 8 ... -> N .

Поскольку каждая вершина будет объединена в большинстве log(N) случаев, количество слияний для всех вершин равно N log(N) . Конечная сложность заключается O(N log N) в следующем .