Submission #60959061

---

Source Code Expand

#include "bits/stdc++.h"
#include <chrono>
using namespace std;

#define LL long long
#define mod 998244353ll
#define PI acos(-1.0)
#define set0(ar) memset(ar, 0, sizeof ar)
#define setinf(ar) memset(ar, 126, sizeof ar)

inline LL bigmod(LL p, LL e, LL M) {
  LL r = 1;
  for (; e > 0; e >>= 1, p = (p * p) % M)
    if (e & 1) r = (r * p) % M;
  return r;
}
inline LL modinverse(LL a, LL M) { return bigmod(a, M - 2, M); }

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<int> vc[300001];
int res = 1;
void dfs(int c, int p) {
  for(int v: vc[c]) {
    if(v == p) continue;
    dfs(v, c);
  }

  vector<int> vp;
  for(int v: vc[c]) {
    vp.push_back(vc[v].size() - 1);
  }
  sort(vp.begin(), vp.end());
  for(int i = 0; i < vp.size(); i++) {
    res = max(res, (int)(vp.size()-i) * (vp[i]+1) + 1);
  }
}

void solve() {
  int n; cin >> n;
  for(int i = 0; i < n-1; i++) {
    int x, y; cin >> x >> y;
    vc[x].push_back(y);
    vc[y].push_back(x);
  }
  dfs(1, 0);
  cout << n-res << endl;

}


int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int T = 1;
  //cin >> T; 
  for (int ts = 1; ts <= T; ts++) {
    //cout << "Case " << ts << ": ";
    solve();
  }
  
}

Submission Info

Compile Error

Main.cpp: In function ‘void dfs(int, int)’:
Main.cpp:34:20: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   34 |   for(int i = 0; i < vp.size(); i++) {
      |                  ~~^~~~~~~~~~~

Judge Result