题目
题目描述
奶牛Bessie令人惊讶地精通计算机。她在牛棚的电脑里用一组文件夹储存了她所有珍贵的文件，比如：
bessie/
folder1/
file1
folder2/
file2
folder3/
file3
file4
只有一个“顶层”的文件夹，叫做bessie。
Bessie可以浏览任何一个她想要访问的文件夹。从一个给定的文件夹，每一个文件都可以通过一个“相对路径”被引用。在一个相对路径中，符号“..”指的是上级目录。如果Bessie在folder2中，她可以按下列路径引用这四个文件：
../file1
file2
../../folder3/file3
../../file4
Bessie想要选择一个文件夹，使得从该文件夹出发，对所有文件的相对路径的长度之和最小。
输入描述
第一行包含一个整数N（2≤N≤100,000），为所有文件和文件夹的总数量。为了便于输入，每个对象（文件或文件夹）被赋予一个唯一的1至N之间的ID，其中ID 1指的是顶层文件夹。
接下来有N行。每行的第一项是一个文件或是文件夹的名称。名称仅包含小写字母a-z和数字0-9，长度至多为16个字符。名称之后是一个整数m。如果m为0，则该对象是一个文件。如果m>0，则该对象是一个文件夹，并且该文件夹下共有m个文件或文件夹。在m之后有m个整数，为该文件夹下的对象的ID。
输出描述
输出所有文件的相对路径的长度之和的最小值。注意这个值可能超过32位整数的表示范围。
示例1
输入
8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0
输出
42
说明
这个输入样例描述了上面给出的样例目录结构。
最优解是选择folder1。从这个文件夹出发，相对路径分别为：
file1
folder2/file2
../folder3/file3
../file4
题解
知识点：树形dp。
考虑树形dp，二次扫描+换根法。
设 \(Size[u]\) 表示为以 \(u\) 为根的子树叶节点数，\(f[u]\) 表示以 \(u\) 为根的子树的路径总长度（\(u\) 文件名不包括在路径中）。转移方程为：
\[f[u] = \sum \big(f[v_i] + Size[v_i] \cdot (a[v_i]+1) \big) \]表示 \(v_i\) 子树下所有叶子节点的路径长度（不包括 \(v_i\) 文件名）\(f[v_i]\) ，都加上一段到文件夹 \(v_i\) 的长度 \(a[v_i]+1\) （文件名加一个斜杠）。
随后把通过子树的答案处理成整个树的答案，设 \(ff[u]\) 表示为以 \(u\) 为起点的路径总长度。转移方程为：
\[ff[v] = \left \{ \begin{aligned} &ff[u] - Size[v] \cdot (a[v] + 1) + 3 \cdot (Size[1] - Size[v]) & &,v不是叶子节点\\ &\inf & &,v是叶子节点 \end{aligned} \right. \]叶子节点不能作为起点直接赋值无穷大，不影响其他节点求值，还方便最后处理最小值。可以通过 \(f[v] = 0\) 来判断是叶子节点，也可以 \(g[v].size = 1\) 来判断。
非叶子节点可以作为起点。当起点从 \(u\) 改到 \(v\) ， \(v\) 子树的叶子节点需要减去 \(v\) 的文件名长度 \(Size[v] \cdot (a[v]+1)\)，其他叶子节点需要加上从 \(v\) 回溯到 \(u\) 的路径 ../ 长度 \(3 \cdot (Size[1]-Size[v])\) ，最后就得到 \(ff[v]\) 的答案。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100007];
vector<int> g[100007];
ll Size[100007], f[100007], ff[100007];///以u为根的子树叶节点数，以u为根的子树的路径总长度，以u为起点的路径总长度
ll ans = ~(1LL << 63);
void dfs1(int u, int fa) {
for (auto v : g[u]) {
if (v == fa) continue;
dfs1(v, u);
Size[u] += Size[v];
f[u] += f[v] + Size[v] * (a[v] + 1);///每条到叶子的路径加名字长度+一个斜杠，斜杠答案时候能删掉
}
}
void dfs2(int u, int fa) {
for (auto v : g[u]) {
if (v == fa) continue;
if (f[v]) ff[v] = ff[u] - Size[v] * (a[v] + 1) + (Size[1] - Size[v]) * 3;///父节点全体路径减去自己的路径加上从自己这里到父节点的路径
else ff[v] = ~(1LL << 63);
dfs2(v, u);
}
ans = min(ans, ff[u]);
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int u = 1;u <= n;u++) {
string s;
cin >> s;
a[u] = s.size();
int m;
cin >> m;
if (!m) Size[u] = 1;
for (int j = 1;j <= m;j++) {
int v;
cin >> v;
g[u].push_back(v);
g[v].push_back(u);
}
}
dfs1(1, 0);
//for (int i = 1;i <= n;i++) cout << Size[i] << ' ';
//for (int i = 1;i <= n;i++) cout << f[i] << ' ';
ff[1] = f[1];
dfs2(1, 0);
//for (int i = 1;i <= n;i++) cout << ff[i] << ' ';
cout << ans - Size[1] << '\n';///路径把末尾的'\'删除，共Size[i]个
return 0;
}
/*
8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0
*/