Codeforces 1009F. Dominant Indices (DSU on Tree)

日付: 12月 20, 2018

[Problem - 1009F - Codeforces](https://codeforces.com/contest/1009/problem/F)
## Problem
Given a tree rooted at vertex 1, for each vertex, find the depth that the number of vertexes is at in the vertex's subtree.

## Solution
This problem can be solved by the technic **DSU on Tree**. During the process of dfs, maintain the depth array (depth as index, number of vertexes as value, which can be stored by `std::map<int,int>` or `std::unordered_map<int,int>`) for the current vertex. This can be merged from all children. The key point is that the result of child is not necessary to be maintained. We always merge small map to large map. If the child's map is larger than the current vertex's map, then **swap** (which is **O(1)** for std containers!) them and continue merging. During merging process the answer can be updated. After merging, do not forget to **clear** child's map.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)

const int N = 1e6 + 5;
int n, D[N], Mv[N], Md[N];
vector<int> G[N];
unordered_map<int, int> M[N];

void dfs(int u, int p) {
    D[u] = D[p] + 1, M[u][D[u]] = 1, Mv[u] = 1, Md[u] = D[u];
    for (auto v : G[u]) if (v != p) {
            dfs(v, u);
            if (M[u].size() < M[v].size()) swap(M[u], M[v]), Mv[u] = Mv[v], Md[u] = Md[v];
            for (auto [dep, cnt] : M[v]) {
                int &tmp = M[u][dep];
                tmp += cnt;
                if (make_pair(tmp, -dep) > make_pair(Mv[u], -Md[u]))
                    Mv[u] = tmp, Md[u] = dep;
            }
            M[v].clear();
        }
}
int main() {
    scanf("%d", &n);
    FI(i, 2, n) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs(1, 0);
    FI(i, 1, n) printf("%d\n", Md[i] - D[i]);
}
```

KONGROOの基地

このブログを検索

Codeforces 1009F. Dominant Indices (DSU on Tree)

コメント

コメントを投稿