题解：P4268 [USACO18FEB] Directory Traversal G
ICU_midway_azuma
·
·
题解
容易看出，所有的目录形成了一棵有根树。
首先假设从 1 号点出发，算出此时长度。
定义 siz_i 为以 i 为根的子树中文件的数量，tot 为所有文件的数量。
假设我们已经知道了从节点 u 出发时的答案 cnt，那么将出发点变为其子节点 v，节点 v 下包含的所有文件都长度都会减少 |name_v|+1，而不在 v 节点下的所有文件访问距离都会增加 3（需要多访问一次父目录）。
因此，从 u 到 v，v 节点的答案即是：
从 $1$ 号点出发，不断访问子节点，比较每个子节点的大小即可。
____
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
string name;
vector<int>son;
int soncnt;
}a[100005];
int siz[100005];
int fcnt;
int cnt=0,ans=LLONG_MAX;
void dfs(int now,int fa,int dis){
if(a[now].soncnt==0){
siz[now]=1;
cnt+=dis-1;
return;
}
for(int i=0;i<a[now].soncnt;i++){
int v=a[now].son[i];
if(v==fa)continue;
dfs(v,now,dis+1+a[v].name.length());
siz[now]+=siz[v];
}
}
void dfs2(int now,int fa,int discnt){
ans=min(ans,discnt);
for(int i=0;i<a[now].soncnt;i++){
int v=a[now].son[i];
if(v==fa)continue;
// if(a[v].soncnt==0)continue;
dfs2(v,now,discnt-(siz[v]*(a[v].name.length()+1-(a[v].soncnt==0)))+(fcnt-siz[v])*3);
}
}
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].name>>a[i].soncnt;
for(int j=1;j<=a[i].soncnt;j++){
int x;
cin>>x;
a[i].son.push_back(x);
}
if(a[i].soncnt==0)fcnt++;
}
dfs(1,0,0);
dfs2(1,0,cnt);
cout<<ans;
return 0;
}
/*
2
folder1 1 2
file1 0
1
file1 0
*/
```