luogu4268 Directory Traversal (dfs)

题意：给一个树状的文件结构，让你求从某个文件夹出发访问到所有文件，访问路径字符串长度之和的最小值，其中，访问父节点用..表示，两级之间用/分割

做两次dfs，第一次算DownN[x]和DownS[x]，分别代表从x/访问到它子树中的文件个数和长度之和

第二次算UpN[x]和UpS[x]，分别代表从x/访问到不在它子树中（也就是要先往上走）的文件个数和长度之和。

最后某个点的答案就是DownS[x]+UpS[x]，取最小即可。

（由于我的zz写法，还需要再单独算一下根的答案）

 #include<bits/stdc++.h>

 #define ll long long

 #define pa pair<int,int>

 using namespace std;

 const int maxn=;

 ll rd(){

     ll x=;char c=getchar();

     while(c<''||c>'') c=getchar();

     while(c>=''&&c<='') x=x*+c-'',c=getchar();

     return x;

 }

 ll dws[maxn],dwn[maxn],ups[maxn],upn[maxn],ans;

 int fa[maxn],son[maxn][],sonh[maxn],sct;

 int N,v[maxn];char ch[];bool isdir[maxn];

 inline void adson(int f,int s){

     son[sct][]=s;son[sct][]=sonh[f];sonh[f]=sct++;fa[s]=f;

 }

 void dfs1(int x){

     for(int i=sonh[x];i!=-;i=son[i][]){

         int s=son[i][];

         dfs1(s);dwn[x]+=dwn[s];

         dws[x]+=dwn[s]*(v[s]+isdir[s])+dws[s];

     }

 }

 void dfs2(int x){

     for(int i=sonh[x];i!=-;i=son[i][]){

         int s=son[i][];if(!isdir[s]) continue;

         upn[s]=upn[x]+dwn[x]-dwn[s];

         ups[s]=ups[x]+*upn[s]+dws[x]-dws[s]-dwn[s]*(v[s]+isdir[s]);

         dfs2(s);

         //printf("%d-ans:%d upn:%d ups:%d dwn:%d dws:%d \n",s,ups[s]+dws[s],upn[s],ups[s],dwn[s],dws[s]);

         ans=min(ans,ups[s]+dws[s]);

     }

 }

 int main(){

     int i,j,k;

     N=rd();memset(sonh,-,sizeof(sonh));

     for(i=;i<=N;i++){

         scanf("%s",ch);

         v[i]=strlen(ch);j=rd();

         if(!j) dwn[i]=;else isdir[i]=;

         for(k=;k<=j;k++) adson(i,rd());

     }ans=2e13;

     dfs1();dfs2();

     printf("%lld\n",min(ans,dws[]));

 }