# Untitled

a guest
Jun 22nd, 2019
923
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. #define int long long
3. #define double long double
4. using namespace std;
5. int INF = 1e18;
6. double DINF = 1e18;
7. vector<vector<int> > data;
8. int ans = INF;
9. vector<int> dp, sz;
10. int n;
11. struct Line{double k; double b; double l; double r;};
12. vector<Line> cht;
14. int L = 0, R = cht.size();
15. double cp = x;
16. while (R-L>1){
17. int M = (L+R)/2;
18. if (cht[M].r >= cp) L = M;
19. else R = M;
20. }
21. int K = cht[L].k, B = cht[L].b;
22. return K*x+B;
23. }
24. double intersect(Line &a, Line &b){
25. if (a.k == b.k) return -DINF;
26. double db = a.b - b.b;
27. double dk = b.k - a.k;
28. return db/dk;
29. }
30. void add(double k, double b){
31. Line nl = {k, b, -DINF, DINF};
32. while (cht.size()){
33. double inter = intersect(nl, cht.back());
34. if (inter <= cht.back().l){
35. cht.pop_back();
36. }
37. else{
38. cht.back().r = inter;
39. nl.l = inter;
40. cht.push_back(nl);
41. break;
42. }
43. }
44. if (!cht.size()) cht.push_back(nl);
45. }
46. void calc(int vertex, int last){
47. vector<pair<int, int> > children;
48. int cur=0;
49. for (int i=0; i < data[vertex].size(); i++){
50. int to = data[vertex][i];
51. if (to == last) continue;
52. children.push_back({sz[to], dp[to]});
53. cur++;
54. }
55. if (cur==1) return;
56. sort(children.begin(), children.end(), greater<pair<int, int> > ());
57. for (int i=0; i < children.size(); i++){
58. int SZ = children[i].first, DP = children[i].second;
59. if (i > 0){
61. ans = min(ans, res + DP + n*n + SZ*SZ - 2*n*SZ);
62. }
63. int K = 2*SZ;
64. int B = DP+SZ*SZ-2*n*SZ;
66. }
67. }
68. void dfs(int vertex, int last){
69. sz[vertex] = 1;
70. for (int i=0; i < data[vertex].size(); i++){
71. int to = data[vertex][i];
72. if (to == last) continue;
73. dfs(to, vertex);
74. sz[vertex] += sz[to];
75. }
76. if (sz[vertex] == 1) dp[vertex] = 1;
77. else{
78. dp[vertex] = INF;
79. for (int i=0; i < data[vertex].size(); i++){
80. int to = data[vertex][i];
81. if (to == last) continue;
82. dp[vertex] = min(dp[vertex], dp[to] + (sz[vertex] - sz[to]) * (sz[vertex] - sz[to]));
83. }
84. }
85. calc(vertex, last);
86. }
87. main() {
88. ios_base::sync_with_stdio(false), cin.tie(0);
89. cin >> n;
90. data.resize(n, {});
91. dp.resize(n, -1);
92. sz.resize(n, -1);
93. for (int i=0; i < n-1; i++){
94. int u, v;
95. cin >> u >> v;
96. data[u-1].push_back(v-1), data[v-1].push_back(u-1);
97. }
98. if (n==2){
99. cout << 2;
100. return 0;
101. }
102. int father = -1;
103. for (int i=0; i < n; i++){
104. if (data[i].size() > 1) father = i;
105. }
106. dfs(father, -1);
107. int res = 2*n*(n-1) - (ans - n);
108. cout << res/2;
109. return 0;
110. }