ferinの競プロ帳

競プロについてのメモ

APC001 E - Antennas on Tree

問題ページ
E - Antennas on Tree

考えたこと

  • 次数が大きい頂点にアンテナを置いても同じ距離の頂点が大量にできるだけなので次数が小さい頂点に置いた方がよさそう
  • 次数が大きいウニみたいなグラフがあったときどうするか考える
  • ウニの中央の頂点に置くのは無意味で1つを除いた葉全てにアンテナを置くしかなさそう
  • ウニの葉だった頂点からさらにグラフが伸びてる状態を考えるとウニの葉だった頂点を根とする部分木のどれかにアンテナが置かれていればウニの部分に関しては条件を満たせそう
  • ある頂点の子について条件を満たしたいとき、一つの子を除いて部分木のいずれかの頂点にアンテナが置かれている必要がある
  • 子が全て葉の頂点があったら(葉の数-1)個アンテナを置くしかない
  • 一般化するとその頂点を根とした部分木に置くアンテナの数は(子のアンテナの数)+(今までにアンテナが置かれていない子の数-1)個になる
  • 葉から順番に計算していけばいいのでDFSをする
  • 根の次数が小さいケースだとだめそうだったので次数が最大の頂点を根としてDFSをした

雰囲気でやった部分が当たっていたり方針ガチャSSRを引いた 木DP系でどうするか考えるときのグラフの例でウニは考えるべきなのかもしれない?

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

VI g[100010];
int d[100010];
int dfs(int x, int p) {
  int leaf = 0, ret= 0;
  for(int i: g[x]) {
    if(i == p) continue;
    if(g[i].size() == 1) {leaf++; continue;}
    int tmp = dfs(i, x);
    if(tmp == 0) leaf++;
    ret += tmp;
  }
  ret += max(0LL, leaf - 1);
  // cout << x << " " << ret << endl;
  return ret;
}

signed main(void)
{
  int n;
  cin >> n;
  REP(i, n-1) {
    int a, b;
    cin >> a >> b;
    g[a].PB(b);
    g[b].PB(a);
  }

  int root = -1, ma = -1;
  REP(i, n) {
    if((int)g[i].size() > ma) ma = (int)g[i].size(), root = i;
  }
  cout << max(1LL, dfs(root, -1)) << endl;

  return 0;
}