• 直径
• 点覆盖集
• 路径覆盖
• 支配集

难度：2
前提：动态规划
后继：

资料：

• …

• https://cses.fi/problemset/task/1133

  #include <lastweapon/io>
  
  using namespace lastweapon;
  
  const int N = int(2e5) + 9;
  
  int n, h[N]; LL f[N], g[N];
  VVI v;
  
  void dfs1(int r, int p = -1) {
      for(int& a : v[r]) if (a != p) {
          dfs1(a, r);
          h[r] += h[a];
          f[r] += f[a] + h[a];
      }
      h[r]++;
  }
  
  void dfs2(int r, int p = -1) {
      for(int& a : v[r]) if (a != p) {
          g[a] = (f[r] - (f[a] + h[a])) + g[r] + (n - h[a]);
          dfs2(a, r);
      }
  }
  
  int main() {
  
  #ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin);
  //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
  #endif
  
      RD(n);
      v.resize(n);
      int a, b;
      while(cin >> a >> b) {
          v[a-1].PB(b-1);
          v[b-1].PB(a-1);
      }
      dfs1(0);
      dfs2(0);
      REP(i, n) printf("%lld ", f[i] + g[i]);
  }
  
  

• https://usaco.guide/problems/ac-subtree/solution

  #include <lastweapon/io>
  #include <lastweapon/number>
  
  using namespace lastweapon;
  
  const int N = int(1e5) + 9;
  
  VI adj[N]; Int f[N], fl[N], fr[N], g[N];
  int n;
  
  void dfs1(int u = 0, int p = -1) {
      f[u] = 1;
      for(auto& v: adj[u]) if (v != p) {
          dfs1(v, u);
          fl[v] = f[u];
          f[u] *= f[v] + 1;
      }
      f[u] = 1;
      for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {
          int v = *it; if (v == p) continue;
          fr[v] = f[u];
          f[u] *= f[v] + 1;
      }
  }
  
  void dfs2(int u = 0, int p = -1) {
      for(auto& v: adj[u]) if (v != p) {
          g[v] = (g[u] + 1) * fl[v] * fr[v]; //f[u] / (f[v] + 1);
          dfs2(v, u);
      }
  }
  
  int main() {
  
  #ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin);
  //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
  #endif
  
      RD(n, MOD); DO(n - 1) {
          int a, b; RD(a, b); --a; --b;
          adj[a].PB(b);
          adj[b].PB(a);
      }
  
      dfs1(); dfs2();
  
      REP(i, n) printf("%d\n", f[i] * (g[i] + 1));
  }
  
  

• https://codeforces.com/contest/1187/problem/E

习题：

• SPOJ PT07Z. Longest path in a tree 树的直径
• Codeforces Round AIM Tech Round 3 Problem C. Centroids
• HDU 2196. Computer
• HDU 5834. Magic boy Bi Luo with his excited tree
• http://user.qzone.qq.com/251815992/blog/1410720943
• 2014-2015 ACM-ICPC, Asia Mudanjiang Regional Contest, Problem F. Fiber-optic Network

Posted by xiaodao
Category: 动态规划