【树形dp】【CF161D】distance on a tree + 【P1352】没有上司的舞会

T1题面：

　输入点数为N一棵树

　求树上长度恰好为K的路径个数

　(n < 1e5, k < 500)

　　这是今天的考试题，也是一道假的紫题，因为我一个根本不会dp的蒟蒻只知道状态就一遍A掉了……（然后我当时不会……emm）

　　考虑f[i][j]表示点i为根的子树中深度为j的点的个数，初始设置f[i][0] = 1。转移的时候，每搞完一棵子树就用这棵子树内的数据用乘法原理更新ans，然后再把它的贡献累加给根，这样可以保证统计不重不漏。

　　也可以用点分治来做。

代码：

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #define maxn 50010  
  4. using namespace std;  
  5. template <typename T>  
  6. void read(T &x) {  
  7.     x = 0;  
  8.     int f = 1;  
  9.     char ch = getchar();  
  10.     while (!isdigit(ch)) {  
  11.         if (ch == '-')  
  12.             f = -1;  
  13.         ch = getchar();  
  14.     }  
  15.     while (isdigit(ch)) {  
  16.         x = x * 10 + (ch ^ 48);  
  17.         ch = getchar();  
  18.     }  
  19.     x *= f;  
  20.     return;  
  21. }  
  22. void open_file(string s) {  
  23.     string In = s + ".in", Out = s + ".out";  
  24.     freopen(In.c_str(), "r", stdin);  
  25.     freopen(Out.c_str(), "w", stdout);  
  26. }  
  27.   
  28. int head[maxn], top, n, k;  
  29. struct E {  
  30.     int to, nxt;  
  31. } edge[maxn << 1];  
  32. inline void insert(int u, int v) {  
  33.     edge[++top] = (E) {v, head[u]};  
  34.     head[u] = top;  
  35. }  
  36. int f[maxn][510];//第二维j表示深度为j的点数   
  37. long long ans;  
  38. void dp(int u, int pre) {  
  39.     for (int i = head[u]; i; i = edge[i].nxt) {  
  40.         int v = edge[i].to;  
  41.         if (v == pre)  
  42.             continue;  
  43.         dp(v, u);  
  44.         for (int i = 0; i < k; ++i) //先统计答案   
  45.             ans += f[u][i] * f[v][k-i-1];  
  46.         for (int i = 1; i <= k; ++i) //算贡献   
  47.             f[u][i] += f[v][i-1];  
  48.     }  
  49.     return;  
  50. }  
  51. int main() {  
  52. //  open_file("distance");  
  53.     read(n), read(k);  
  54.     int u, v;  
  55.     for (int i = 1; i < n; ++i) {  
  56.         read(u), read(v);  
  57.         insert(u, v), insert(v, u);  
  58.     }  
  59.     for (int i = 1; i <= n; ++i)   
  60.         f[i][0] = 1;  
  61.     dp(1, 0);  
  62.     printf("%I64d ", ans);  
  63.     return 0;  
  64. }  

　　T2题面就不放了。这是一道树形dp的入门题。

　　考虑每个点可以有选与不选两种状态，设f[i][0]表示不选这个点后以该点为根的最大贡献，f[i][1]表示选。我们可以自底向顶转移，有f[u][1] = w[u] + sigma(f[v][0])，f[u][0] = sigma(max(f[v][0], f[v][1])。注意第二个方程中选不选子节点是都可以的，要注意这种比较松的限制可能遗漏。

代码：

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #define maxn 6010  
  4. template <typename T>  
  5. void read(T &x) {  
  6.     x = 0;  
  7.     int f = 1;  
  8.     char ch = getchar();  
  9.     while (!isdigit(ch)) {  
  10.         if (ch == '-')  
  11.             f = -1;  
  12.         ch = getchar();  
  13.     }  
  14.     while (isdigit(ch)) {  
  15.         x = x * 10 + (ch ^ 48);  
  16.         ch = getchar();  
  17.     }  
  18.     x *= f;  
  19.     return;  
  20. }  
  21. using namespace std;  
  22.   
  23. int head[maxn], top;  
  24. struct E {  
  25.     int to, nxt;  
  26. } edge[maxn << 1];  
  27. inline void insert(int u, int v) {  
  28.     edge[++top] = (E) {v, head[u]};  
  29.     head[u] = top;  
  30. }  
  31. int f[maxn][2], w[maxn], ind[maxn], n, root;  
  32. void dp(int u) {  
  33.     f[u][1] = w[u];  
  34.     for (int i = head[u]; i; i = edge[i].nxt) {  
  35.         int v = edge[i].to;  
  36.         dp(v);  
  37.         f[u][1] += f[v][0];  
  38.         f[u][0] += max(f[v][1], f[v][0]);  
  39.     }  
  40.     return;  
  41. }  
  42. int main() {  
  43.     read(n);  
  44.     for (int i = 1; i <= n; ++i)   
  45.         read(w[i]);  
  46.     int u, v;  
  47.     for (int i = 1; i < n; ++i) {  
  48.         read(u), read(v);  
  49.         insert(v, u);  
  50.         ++ind[u];  
  51.     }  
  52.     for (int i = 1; i <= n; ++i)  
  53.         if (!ind[i]) {  
  54.             root = i;  
  55.             break;  
  56.         }  
  57.     dp(root);  
  58.     printf("%d", max(f[root][0], f[root][1]));  
  59.     return 0;  
  60. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/TY02/p/11203683.html