https://ac.nowcoder.com/acm/problem/247496
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int N = 3e5 + 10; 5 6 typedef long long LL; 7 //本题的思路就是在与反转操作的理解, 以及这种操作其实等价于将树任意修改, 具体为什么请看视频 8 int h[N], e[N], w[N], ne[N], idx; 9 int n, s[N]; 10 LL res;//注意数据范围, 经常犯错误, 下一次注意一下 11 12 int dfs(int u) { 13 s[u] ++ ; 14 for (int i = h[u]; i != -1; i = ne[i]) { 15 int j = e[i]; 16 s[u] += dfs(j); 17 } 18 return s[u]; 19 }//这里如果用有向图的方式来存储的话就不用bool st[]了 20 21 void add(int a, int b) { 22 e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; 23 } 24 25 int main() { 26 cin >> n; 27 for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]); 28 sort(w + 1, w + 1 + n); 29 // for (int i = 1; i <= n; i ++ ) printf("%d ", w[i]); 30 memset(h, -1, sizeof h); 31 for (int i = 1; i <= n - 1; i ++ ) { 32 int t; 33 scanf("%d", &t); 34 add(t, i + 1);//注意这里用有向图的存储方式, 不然会tle 35 } 36 dfs(1); 37 sort(s + 1, s + 1 + n); 38 // for (int i = 1; i <= n; i ++ ) printf("%d ", s[i]); 39 for (int i = 1; i <= n; i ++ ) res += (LL)s[i] * w[i]; 40 41 cout << res << endl; 42 return 0; 43 }
关键点是想明白为什么反转操作等价于对权值任意排列 , 然后就是每一个结点的size怎么用dfs求出来 , 这一道题我用y总的方法发现用无向图的存储和遍历方式会超时 , 可是用有向图的方法就不会出问题
就很奇葩
标签:有向图,idx,int,++,ne,dfs,牛客,64,小白月赛 From: https://www.cnblogs.com/llihaotian666/p/17026073.html