SHARE
TWEET

Untitled

a guest Jun 22nd, 2019 405 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;
  13. int ask(int x){
  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){
  60.             int res = ask(SZ);
  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;
  65.         add(K, B);
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top