Directory Traversal

树上求每个点出发的“路径”总长最短的点的问题，这是比较典型的移根DP的题。

我们看到这个题对于“路径总长”定义是有一些奇怪的，首先路径总长只包含到叶子节点（文件）的，不需要计算到非叶子节点（目录）的。其次，因为每个文件的相对路径长度都包含路上所有目录，所以经过的边和点要多次计算。这个可以通过记录子树中的叶子节点数量（ $\texttt{cnt}[i]$ ）来方便计算。另外，统计文件/目录长度的时候（ $\texttt{len}[i]$ ），把目录的名字长度加一，可以直接把“/”符号包含进去。

具体的DP状态如下：用 $\texttt{dp}[i]$ 表示从 $i$ 出发，访问 $i$ 子树内所有文件的总路径长度。用 $\texttt{dp2}[i]$ 表示从 $i$ 出发，访问整棵树上所有文件的总路径长度。则状态转换为（ $T$ 是总叶子节点数）：

\begin{align} \texttt{dp}[i] &= \sum_{u \in C_i} (\texttt{dp}[u] + \texttt{len}[u] \cdot \texttt{cnt}[u]) \\ \texttt{dp2}[u] &= \texttt{dp}[u] + \texttt{dp2}[i] - (\texttt{dp}[u] + \texttt{len}[u] \cdot \texttt{cnt}[u]) + 3 \cdot (T - \texttt{cnt}[u]) \\ &= \texttt{dp2}[i] - \texttt{len}[u] \cdot \texttt{cnt}[u] + 3 \cdot (T - \texttt{cnt}[u]) \end{align}

公式 $2$ 中， $\texttt{dp}[u]$ 是从 $u$ 出发到子树内的路径总长， $\texttt{dp2}[i] - (\texttt{dp}[u] + \texttt{len}[u] \cdot \texttt{cnt}[u])$ 是从父母节点 $i$ 出发到除 $u$ 之树外的原来的路径总长（从 $i$ 出发访问）， $3 \cdot (T - \texttt{cnt}[u])$ 是要把这些路径变成从 $u$ 出发，前面需要加上../的总长度。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
int len[100005];    // file/directory name length
vector<int> adj[100005];
int cnt[100005];    // number of leaves in subtree
ll dp[100005];     // dp[i]: total length of relative paths from i in subtree
ll dp2[200005];    // dp2[i]: total length of relatives paths from i to whole tree
ll ans = 1e18;
 
void dfs1(int s, int e) {
    if (adj[s].empty())
        cnt[s] = 1;
    for (int u: adj[s]) {
        dfs1(u, s);
        cnt[s] += cnt[u];
        dp[s] += (ll)len[u]*cnt[u] + dp[u]; //      folder/dp[u]
    }
}
 
void dfs2(int s, int e) {
    for (int u: adj[s]) {       // root change from s to u
        if (adj[u].empty()) continue;
        dp2[u] = dp[u] + dp2[s] - (dp[u] + (ll)len[u]*cnt[u]) + (cnt[0] - cnt[u])*3;
        ans = min(ans, dp2[u]);
        dfs2(u, s);
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        char name[20];
        int t;
        scanf("%s %d", name, &t);
        len[i] = strlen(name) + (t > 0);        // dir name is +1
        for (int j = 0; j < t; j++) {
            int u;
            scanf("%d", &u);
            adj[i].push_back(u-1);
        }
    }
    dfs1(0, -1);        // calc dp[i]
    ans = dp2[0] = dp[0];
    dfs2(0, -1);        // calc dp2[i]
    printf("%lld", ans);
    return 0;
}