牛客小白月赛 64 D题

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总的方法发现用无向图的存储和遍历方式会超时 , 可是用有向图的方法就不会出问题

就很奇葩