NC24263. [USACO 2018 Feb G]Directory Traversal
描述
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
说明:
这个输入样例描述了上面给出的样例目录结构。C++ 解法, 执行用时: 92ms, 内存消耗: 12396K, 提交时间: 2022-02-16 17:05:50
#include <bits/stdc++.h>
#define LL long long
#define siz(a) (son[a].size())
using namespace std;
string s;
LL cnt=0,n,m;
LL f[200000];
LL sz[200000];
LL len[200000];
LL dis[200000];
vector<LL>son[200000];
void dfs(LL x)
{
if (siz(x)==0)
{
dis[x] --;
sz[x]=1;
f[1]+=dis[x];
cnt++;
}
for (LL i=0;i<siz(x);++i)
{
LL y=son[x][i];
dis[y]=dis[x]+len[y]+1;
dfs(y);
sz[x]+=sz[y];
}
}
void dfs2(LL x)
{
for (LL i=0;i<siz(x);++i)
{
LL y=son[x][i];
f[y]=f[x]-(len[y]+1)*sz[y]+3*(cnt-sz[y]);
dfs2(y);
}
}
int main(void)
{
cin>>n;
for (LL i=1;i<=n;++i)
{
cin>>s>>m;
len[i]=s.length();
for (LL j=1,k;j<=m;++j)
{
cin>>k;
son[i].push_back(k);
}
}
dfs(1);
dfs2(1);
LL ans=LONG_LONG_MAX;
for (LL i=1;i<=n;++i)
ans=min(ans,f[i]);
cout<<ans<<endl;
return 0;
}