Submission #41841031

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)(n);i++)
// #define per(i,a,n) for (ll i=n;i-->(ll)(a);)

// 2 * math.log(200000)/math.log(2) = 35.219280948873624
const int lim = 50;
const int INF=0x3f3f3f3f;
ll read(){ll r;scanf("%lld",&r);return r;}

vector<int> e[200010];
array<vector<int>,3> dp[200010]; // dp[u][与子树连的个数][向下最多颜色] = 以下已有贡献最多颜色
auto chmin=[](auto&a,const auto &b){a=min(a,b);};
int sz[200010];
auto _=[](int siz){return min(siz,lim);};

void dfs(int u,int f){
  sz[u] = 1; // 重用
  rep(c,0,3) dp[u][c] = vector(1+2,INF);
  dp[u][0][1] = 1;

  auto merge=[&](int v){
    array<vector<int>,3> ndp;
    rep(c,0,3) ndp[c] = vector(_(sz[u]+sz[v])+1,INF);
    rep(i,1,_(sz[u])+1) rep(c0,0,3) rep(j,1,_(sz[v])+1) rep(c1,0,3) {
      chmin(ndp[c0  ][max(i,j+1)], max({dp[u][c0][i], dp[v][c1][j], i+j})); // 不连u-v
      if(c0 < 2 and c1 < 2){
      chmin(ndp[c0+1][max(i,j  )], max({dp[u][c0][i], dp[v][c1][j], i+j-1})); // 连 u-v
      }
    }
    sz[u] += sz[v];
    rep(c,0,3) {
      dp[u][c].resize(_(sz[u])+2,INF);
      rep(j,1,_(sz[u])+1) dp[u][c][j] = ndp[c][j];
    }
  };

  for(auto v:e[u]) if(v!=f){
    dfs(v,u);
    merge(v);
  }
}

int main(){
  int n=read();
  rep(i,1,n){
    int u=read();
    int v=read();
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1,-1);
  int ans = INF;
  rep(c,0,3) rep(i,1,_(sz[1])+1) chmin(ans, dp[1][c][i]);
  assert(ans <= lim);
  printf("%d\n",ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:10:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   10 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result