[每日一题] [NC15748] 旅游

https://ac.nowcoder.com/acm/problem/15748

题目大意：给定一个树，每天选择一个点访问，每次访问的时候标记其邻居。要求每天不能访问标记过的点。最多可以访问多少天。

题意就是选择一个maximum independent set，对于树来说就比较简单用tree dp即可。就是考虑每个node选／不选的MIS，然后很容易用孩子表示根。最后返回root(s)选择的MIS。

注意会被卡常，也需要开fast IO.

#define MAXN 500005
VI children[MAXN];
int visited[MAXN];
int unchosen[MAXN];
VI neighbors[MAXN];

void helper(int s) {
  if (visited[s]) return;
  for (int nbr : children[s]) {
    helper(nbr);
  }
  visited[s] = 1;
  unchosen[s] = 0;
  for (int nbr : children[s]) {
    visited[s] += unchosen[nbr];
    unchosen[s] += max(unchosen[nbr], visited[nbr]);
  }
}

int doit(int n, int s) {
  REP(i,n){
    visited[i]=0;
  }
  helper(s);
  return visited[s];
}

int main(int argc, char* argv[]) {
  /* Do not use for codejam. */
  /* ios_base::sync_with_stdio(false); cin.tie(NULL); */
  readint(n);
  readint(s);--s;
  REP(i,n-1){
    read2int(u,v);--u;--v;
    neighbors[u].PB(v);
    neighbors[v].PB(u);
  }
  que<int> frontier;
  frontier.push(s);
  visited[s]=1;
  while (!frontier.empty()) {
    int curr = QPOP(frontier);
    for (int nbr : neighbors[curr]) {
      if(!visited[nbr]){
        visited[nbr]=1;
        frontier.push(nbr);
        children[curr].PB(nbr);
      }
    }
  }
  printint(doit(n, s));
  return 0;
}