重光分解问题

Question

我正在研究 HLD，我发现我需要 4 个东西：

给定一个节点，知道它的链；
给定一个节点，知道它在链中的位置；
给定一条链，知道它的头；
给定一条链，知道它的长度。

这4件事我能做3件，但我做不到第二件。

我在树上使用单个 dfs 做到了，我想知道是否（以及如何）在我的代码中添加一些东西来解决第二个问题 .

代码如下：

#define maxn 1010

int SizeOf[maxn], SpecialChildOf[maxn],
    ChainOf[maxn], SizeOfChain[maxn], HeadOfChain[maxn];
int chain = 0;
vector<int> T[maxn];

void dfs(int u){
    SizeOf[u] = 1;
    int adj = T[u].size();
    if(!adj){
        ChainOf[u] = chain;
        SpecialChildOf[u] = -1;
        HeadOfChain[chain] = u;
        SizeOfChain[chain]++;
        return;
    }
    dfs(T[u][0]);
    int specialChild = T[u][0];
    SizeOf[u] += SizeOf[specialChild];

    for(int i = 1; i < adj; i++){
        int v = T[u][i];
        chain++;
        dfs(v);
        if(SizeOf[v] > SizeOf[specialChild]) specialChild = v;
        SizeOf[u] += SizeOf[v];
    }

    SpecialChildOf[u] = specialChild;
    ChainOf[u] = ChainOf[specialChild];
    SizeOfChain[ChainOf[u]]++;
    HeadOfChain[ChainOf[u]] = u;
}

它有什么作用？这是一个简单的 dfs，你从链 0 开始，在不改变当前链的情况下一直沿着树向下走。当你到达一个叶节点时，你指定这个节点是当前链的最后一个元素（并将当前链的大小增加 1）并返回到前一个节点。当你返回时，你会看到该节点的其他子节点，传递给每个子节点一个不同的链，从所有节点返回后，所有子节点中最大的子链成为当前节点的链，然后它 returns.

Answer 1

一种方法是通过在 return 语句之前添加代码来存储到链末端的距离：

DistanceToEnd[u] = SizeOfChain[ChainOf[u]];

深度优先搜索完成后，您就可以通过以下方式计算链中的位置：

distanceToStart = SizeOfChain[ChainOf[u]] - DistanceToEnd[u];

重光分解问题

Heavy Light Decomposition Issue

algorithm

tree

depth-first-search