洛谷 P3478 POI 2008 STA-Station

url: https://www.luogu.com.cn/problem/P3478

tag:
树形DP,POI,2008

思路:
利用两次dfs,第一次求出以1为根节点时深度和,以及各个节点为根时的子树大小,之后利用第二次dfs求出每个节点为根时的深度和。这个方法称为二次扫描。

代码:

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <cstring>
  5. using namespace std;
  6. const int N = 1e6 + 10;
  7. int h[N], e[N * 2], ne[N * 2], idx;
  8. int n;
  9. long long res, id;
  10. long long d[N], s[N], f[N];
  11. void add(int a, int b)
  12. {
  13. e[idx] = b;
  14. ne[idx] = h[a];
  15. h[a] = idx ++;
  16. }
  17. void dfs(int u, int fa)
  18. {
  19. s[u] = 1; d[u] = d[fa] + 1;
  20. for (int i = h[u]; ~i; i = ne[i])
  21. {
  22. int j = e[i];
  23. if (j == fa) continue;
  24. dfs(j, u);
  25. s[u] += s[j];
  26. }
  27. }
  28. void dfs2(int u, int fa)
  29. {
  30. for (int i = h[u]; ~i; i = ne[i])
  31. {
  32. int j = e[i];
  33. if (j == fa) continue;
  34. f[j] = f[u] + n - 2 * s[j];
  35. dfs2(j, u);
  36. }
  37. }
  38. int main()
  39. {
  40. cin >> n;
  41. memset(h, -1, sizeof h);
  42. for (int i = 0; i < n - 1; i ++)
  43. {
  44. int a, b;
  45. cin >> a >> b;
  46. add(a, b), add(b, a);
  47. }
  48. dfs(1, 0);
  49. for (int i = 1; i <= n; i ++) f[1] += d[i];
  50. dfs2(1, 0);
  51. for (int i = 1; i <= n; i ++) if (f[i] > res) res = f[i], id = i;
  52. cout << id << endl;
  53. return 0;
  54. }
添加新评论