题解

#include <bits/stdc++.h>
using namespace std;
 
#define NMAX 100000
 
struct Node {
  bool isFile;
  vector<Node*> children;
  int namelen;
 
  int numLeaves;
  long long totalSubtreeLen;
 
  long long total;
};
 
Node nodes[NMAX];
 
int n;
int nleaves;
 
void dfs1(Node* node) {
  node->numLeaves = (node->isFile ? 1 : 0);
  node->totalSubtreeLen = 0;
  for (Node* child : node->children) {
    dfs1(child);
    node->numLeaves += child->numLeaves;
    node->totalSubtreeLen += child->totalSubtreeLen + child->numLeaves * (child->namelen + (child->isFile ? 0 : 1));
  }
}
 
void dfs2(Node* node, long long parentlen) {
  node->total = parentlen + node->totalSubtreeLen;
 
  long long plenadd = 0;
  for (Node* child : node->children) {
    plenadd += child->totalSubtreeLen + child->numLeaves * (child->namelen + (child->isFile ? 0 : 1));
  }
  for (Node* child : node->children) {
    dfs2(child, parentlen + plenadd -
      (child->totalSubtreeLen + child->numLeaves * (child->namelen + (child->isFile ? 0 : 1)))
      + 3 * (nleaves - child->numLeaves));
  }
}
 
int main() {
  cin>>n;
  char name[40];
  nleaves = 0;
  for (int i = 0; i < n; i++) {
    cin>>name;
    nodes[i].namelen = strlen(name);
    int k;
    cin>>k;
    nodes[i].isFile = (k == 0);
    if (nodes[i].isFile) {
      nleaves++;
    }
    for (int j = 0; j < k; j++) {
      int id;
      cin>>id;
      nodes[i].children.push_back(&nodes[id-1]);
    }
  }
 
  assert(!nodes[0].isFile);
 
  dfs1(&nodes[0]);
  dfs2(&nodes[0], 0);
  long long ans = nodes[0].total;
  for (int i = 0; i < n; i++) {
    if (!nodes[i].isFile) {
      ans = (ans < nodes[i].total ? ans : nodes[i].total);
    }
  }
  cout<<ans;
}