CF1009F Dominant Indices

直接长链剖分优化。

一个点的答案直接从他的重子节点拖过来，然后暴力合并上其他非重子节点的答案。

每条长链开个数组即可。

复杂度为所有长链的长度和，$O(n)$。

#include <iostream>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 1e6;
int_t depth[LARGE + 1], maxChd[LARGE + 1], maxDepth[LARGE + 1];
std::vector<int_t> graph[LARGE + 1];
int_t results[LARGE + 1];
void DFS1(int_t vtx, int_t from = -1) {
    if (from == -1) depth[vtx] = 1;
    maxDepth[vtx] = depth[vtx];
    for (int_t to : graph[vtx])
        if (to != from) {
            depth[to] = depth[vtx] + 1;
            DFS1(to, vtx);
            maxDepth[vtx] = std::max(maxDepth[vtx], maxDepth[to]);
            if (maxDepth[to] > maxDepth[maxChd[vtx]]) {
                maxChd[vtx] = to;
            }
        }
}
//当前链使用的状态数组为arr
void DFS2(int_t vtx, int_t from, int_t* arr) {
    arr[0] += 1;
    int_t& result = ::results[vtx];
    //递归重子节点
    if (maxChd[vtx]) {
        DFS2(maxChd[vtx], vtx, arr + 1);
        result = results[maxChd[vtx]] + 1;
    }
    //递归处理其他子节点
    for (int_t to : graph[vtx]) {
        if (to == from || to == maxChd[vtx]) continue;
        int_t* next = new int_t[maxDepth[to] - depth[vtx] + 1];
        std::fill(next, next + maxDepth[to] - depth[vtx] + 1, 0);
        DFS2(to, vtx, next + 1);
        for (int_t i = 1; i <= maxDepth[to] - depth[vtx]; i++) {
            arr[i] += next[i];
            if (arr[i] > arr[result]) {
                result = i;
            } else if (arr[i] == arr[result] && i < result)
                result = i;
        }
    }
    if (arr[result] == 1) result = 0;
}
int n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i++) {
        int from, to;
        scanf("%d%d", &from, &to);
        graph[from].push_back(to);
        graph[to].push_back(from);
    }
    DFS1(1);
#ifdef DEBUG
    for (int_t i = 1; i <= n; i++)
        cout << "maxChd " << i << " = " << maxChd[i] << endl;
#endif
    auto ptr = new int_t[n + 1];
    std::fill(ptr, ptr + n + 1, 0);
    DFS2(1, -1, ptr);
    for (int i = 1; i <= n; i++) {
        printf("%d\n", (int)results[i]);
    }
    return 0;
}