https://www.luogu.org/problemnew/show/P4268

题意：选一个文件夹为当前目录，求到所有文件的需要打的字符数之和最小的那个当前目录。

思路：看成一棵树，文件夹当中间结点，文件当成叶子，求的就是：选一个中间结点，使其到所有叶子的距离和最小。

先求根节点的总路径长度，同时把各结点下叶子总个数求出来，再依次由父节点的总路径长度推出子结点的总路径长度

对于一个结点u，u下面的叶子路径长度全部减去u的长度+1（/），其他不在u下面的叶子结点全部加上3（../）。

注意要开long long。

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000+100

long long n,len[maxn],file[maxn],ans;
vector<long long> son[maxn];

long long dfs(long long u,long long num)
{
	long long ans=0;
	if(son[u].size()==0)return num+len[u];
	for(long long i=0;i<son[u].size();i++)ans+=dfs(son[u][i],num+len[u]+1);
	return ans;
}
long long dfs2(long long u)
{
	if(son[u].size()==0)return 1;
	for(long long i=0;i<son[u].size();i++)file[u]+=dfs2(son[u][i]);
	return file[u];
}
void dfs3(long long u,long long fa_ans)
{
	long long _ans;	
	if(son[u].size()!=0)_ans=fa_ans-file[u]*(len[u]+1)+3*(file[1]-file[u]),ans=min(ans,_ans);
	for(long long i=0;i<son[u].size();i++)dfs3(son[u][i],_ans);
}

int main()
{
//	freopen("input.in","r",stdin);
	char str[1000];long long a,b;
	cin>>n;
	for(long long i=1;i<=n;i++)
	{
		scanf("%s%lld",str,&a);
		len[i]=strlen(str);
		while(a--)
		{
			scanf("%lld",&b);
			son[i].push_back(b);
		}
	}
	dfs2(1);
	long long root=dfs(1,-(len[1]+1));
	ans=root;	
	for(long long i=0;i<son[1].size();i++)dfs3(son[1][i],root);
	cout<<ans<<endl;
	return 0;
}