Descrtiption
奶牛Bessie令人惊讶地精通计算机。她在牛棚的电脑里用一组文件夹储存了她所有珍贵的文件，比如：
bessie/ folder1/ file1 folder2/ file2 folder3/ file3 file4
只有一个“顶层”的文件夹，叫做bessie。
Bessie可以浏览任何一个她想要访问的文件夹。从一个给定的文件夹，每一个文件都可以通过一个“相对路径”被引用。
在一个相对路径中，符号“..”指的是上级目录。如果Bessie在folder2中，她可以按下列路径引用这四个文件：
../file1file2../../folder3/file3../../file4
Bessie想要选择一个文件夹，使得从该文件夹出发，对所有文件的相对路径的长度之和最小。
\(N \leqslant 1e5\)
Solution
\(\,\,\,\,\,\,\,\,\,\,\,\)首先你得需要看懂题面（没看懂再看一次，我可不会解释）。典型的二次换根类题目。设\(len_i\)为点i的名称长度，设\(f_i\)为i到所有叶子点的长度之和，先考虑如何算出根的f值，再考虑如何用一个点更新其儿子，以此类推。
\(\,\,\,\,\,\,\,\,\,\,\,\)根的值很好求，因为只需要往下走。再考虑如何更新儿子。
\(\,\,\,\,\,\,\,\,\,\,\,\) 用这个图打个比方，假设每个点的字符串长度就等于自身编号。我们先预处理出1号点到所有叶子点的总长度，再考虑更新7号点。对于所有在7号点子树内的叶子点，1号点必须先访问到7号点再下走访问各个点，所以7号点访问这些点的总长度=1号点访问的总长度-7号点子树内个数\(\times (len_7+1)\)，而除去7号点子树以外的叶子点只需让7号点先访问到一号点之后就和1号点的访问情况一样了，所以7号点访问这些点的总长度=1号点访问的总长度+(总点数-7号点子树内个数)\(\times 3\)。所以整合起来，7号点访问所有叶子点的总长度=1号点访问的总长度+总点数\(\times3-7\)号点子树内个数\(\times (4+len_7)\)。
#include#include #include #include #define ll long longusing namespace std;const int maxn=1e5;char S[maxn+8];int n,tot,cnt;ll ans;int pre[maxn+8],now[maxn+8],son[maxn+8];int fa[maxn+8],siz[maxn+8],len[maxn+8];ll dep[maxn+8],f[maxn+8]; int read(){ int x=0,f=1;char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f;} void add(int u,int v){ pre[++tot]=now[u]; now[u]=tot; son[tot]=v;} void build(int x){ for (int p=now[x];p;p=pre[p]) { int child=son[p]; fa[child]=x; build(child); dep[x]+=dep[child]+len[x]*siz[child]; siz[x]+=siz[child]; } if (!siz[x]) siz[x]=1,dep[x]=len[x]-1,cnt++;} void solve(int x){ ans=min(ans,f[x]); for (int p=now[x];p;p=pre[p]) { int child=son[p]; if (!dep[child]) continue; f[child]=f[x]-siz[child]*len[child]+3*(cnt-siz[child]); solve(child); }} int main(){ n=read(); for (int i=1;i<=n;i++) { scanf("%s",S);len[i]=strlen(S)+1; int p=read(); for (int j=1;j<=p;j++) { int v=read(); add(i,v); } } build(1);ans=f[1]=dep[1]-len[1]*cnt; solve(1); printf("%lld\n",ans); return 0;}