这里是学习韦神的6道入门树形dp进行入门，本来应放在day12&&13里，但感觉这个应该单独放出来好点。

这里大部分题目都是参考的韦神的思想。

A - Anniversary party

题意：
一个树，每个点有一个“快乐”值，父子结点不能同时快乐，问这个结构的最大快乐值。

Thinking:

思考如何写出树规方程，即思考根与子节点的关系。

dp[i][0]:表示不邀请i员工其子树达到的最大快乐值，dp[i][1]则表示邀请。

这时根与子节点的关系就显然了。

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 using namespace std;

 typedef long long LL;

 #define mst(s, t) memset(s, t, sizeof(s))

 const int INF = 0x3f3f3f3f;

 const int maxn = ;

 vector<int> G[maxn];

 int father[maxn], dp[maxn][];

 void dfs(int root){

     for(int i=; i<G[root].size(); i++){

         dfs(G[root][i]);

     }

     for(int i=; i<G[root].size(); i++){

         dp[root][] += max(dp[G[root][i]][], dp[G[root][i]][]);

         dp[root][] += dp[G[root][i]][];

     }

 }

 int main()

 {

     freopen("in.txt", "r", stdin);

     mst(dp, ); mst(father, -);

     int n;

     scanf("%d", &n);

     for(int i=; i<=n; i++){

         scanf("%d", &dp[i][]);

         G[i].clear();

     }

     int fa, so;

     while(scanf("%d%d", &so, &fa) && fa && so){

         G[fa].push_back(so);

         father[so] = fa;

     }

     int root = ;

     while(father[root] != -)    root=father[root];

     dfs(root);

     printf("%d\n", max(dp[root][], dp[root][]));

     return ;

 }

B - Strategic game

题意：

现在要在一棵树上布置士兵，每个士兵在结点上，每个士兵可以守护其结点直接相连的全部边，问最少需要布置多少个士兵。

这题解法与上题相似。

 dp[root][] += dp[G[root][i]][];

 dp[root][] += min(dp[G[root][i]][], dp[G[root][i]][]);

在读题时想了下结点A的父节点B的变化会影响到A和B的父节点C，会影响到总人数，后来又想了想，这不就是dp要解决的问题呀，在每个阶段做一个决策，以求达到预定的效果。

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 using namespace std;

 typedef long long LL;

 #define mst(s, t) memset(s, t, sizeof(s))

 const int INF = 0x3f3f3f3f;

 const int maxn = ;

 int dp[maxn][], father[maxn];

 vector<int> G[maxn];

 void dfs(int root){

     for(int i=; i<G[root].size(); i++){

         dfs(G[root][i]);

     }

     for(int i=; i<G[root].size(); i++){

         dp[root][] += dp[G[root][i]][];

         dp[root][] += min(dp[G[root][i]][], dp[G[root][i]][]);

     }

 }

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int n;

     while( scanf("%d", &n) != EOF){

         for(int i=; i<=n; i++){

             G[i].clear();

             dp[i][] = ,  dp[i][] = ;

             father[i] = -;

         }

         for(int i=; i<n; i++){

             int root, node, cnt;

             scanf("%d:(%d)",&root, &cnt);

             for(int i=; i<cnt; i++){

                 scanf("%d", &node);

                 G[root].push_back(node);

                 father[node] = root;

             }

         }

         int root = ;

         while(father[root] != -) root=father[root];

         dfs(root);

         printf("%d\n", min(dp[root][], dp[root][]));

     }

     return ;

 }

C - Tree Cutting

题意：

一棵无向树，结点为n(<=10,000)，删除哪些结点可以使得新图中每一棵树结点小于n/2。

Thinking：

真的是菜的无语，面对不会写的题总有懒于思考的毛病。

下面记录解决此题的心得：这题给我一种搜索而非dp的感觉，可能有什么我没发现的深意吧。

在遍历树的过程中，访问每个node，维护两个值：

  1. 所有子树的结点数的最大值childmax
  2. 所有子树(这里包括node)的结点数之和sum。

递归过程中用上一层的sum，不断更新这一层的childmax。

而childmax和sum则共同用来判断这个node是否可以删除。

下面再分析判断条件： childmax<=n/2 && n-sum<=n/2

childmax<=n/2 ：去掉node后，原先node的子树均满足条件。

n-sum<=n/2  ：去掉node后，原先除node和node的所有子树外的树(就当是node的祖先树吧)均满足条件。

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 using namespace std;

 typedef long long LL;

 #define mst(s, t) memset(s, t, sizeof(s))

 const int INF = 0x3f3f3f3f;

 const int maxn = ;

 vector<int> G[maxn];

 int ans[maxn], num, n;

 int dfs(int node, int father){

     int sum = , childmax = ;   //若是叶子结点则return sum=1，否则求其子树(包括自己)的总结点数

     for(int i=; i<G[node].size(); i++){

         if(G[node][i] == father)continue; //因为是树结构，这里可以在无向时避免遍历成环

         int sum_son = dfs(G[node][i], node);

         childmax = max(sum_son, childmax);//所有子树的结点数的最大值

         sum += sum_son;//sum:node的子树的结点数和

     }

     childmax = max(childmax, n-sum);

     if(childmax <= n/){

         /*

          * 当node结点的孩子结点的结点数最大为Sum,若Sum<=n/2,则该点符合条件

          * 因为去掉node后，任意子树结点数<=n/2, max()保证其非子树结点和仍<=n/2

          * 故该点满足条件

         */

         ans[num++] = node;

     }

     return sum;

 }

 int main()

 {

     //freopen("in.txt", "r", stdin);

     scanf("%d", &n);

     for(int i=; i<n-; i++){

         int a, b;

         scanf("%d%d", &a, &b);

         G[a].push_back(b);

         G[b].push_back(a);

     }

     num = ;

     int tmp = dfs(, );

     //cout << n << "==" << tmp << endl; //验证

     sort(ans, ans+num);

     if(num){

         for(int i=; i<num; i++){

             printf("%d\n", ans[i]);

         }

     }else{

         printf("NONE\n");

     }

     return ;

 }

D - Tree of Tree

题意：一棵结点带权树，大小(结点数)为k的子树的权值和最大为多少。

这道题促使我写这篇学习心得，感觉稍微需要点思考的dp题我连思路都看得费劲。博客里的思路真的是想了好久，又找了份前辈的AC代码敲了敲(敲出来竟然连样例都没过，哎)，趁热记录下自己的划水心得。

开始是想到要用状态dp[i]][j]表示node i的 结点数为j的子树 的最大权值和。 但是如何动态规划却没有思路。

这里对每个子节点进行背包dp， dp[j] = max(dp[j], dp[j-w[i]]+v[i]) ，从后往前dp是因为若从后往前会使v的某一个t被重复选取。

这道题整体思路还不清晰，要再多看看。

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 using namespace std;

 typedef long long LL;

 #define mst(s, t) memset(s, t, sizeof(s))

 const int INF = 0x3f3f3f3f;

 const int maxn = ;

 vector<int> G[maxn];

 int dp[maxn][maxn];  //dp[i][j]:node[i]结点数为j的子树的最大权值

 int k, ans, cnt[maxn], weight[maxn];

 int dfs(int node, int father){

     cnt[node] = ;

     for(int i=; i<G[node].size(); i++){

         if(G[node][i] == father) continue;

         cnt[node] += dfs(G[node][i], node);

     }

     dp[node][] = weight[node];

     //这里初始化不能在main()内  ？？

 /*

  *  dp[node][j-t]是之前的子节点为根更新的子树产生的

  *  dp[v][t]是以当前子节点为根的子树产生的

  *  j如果顺序遍历，前面dp[node][j]的更新会影响后面的dp[node][j-t]，导致后面

  *更新dp[node][j]时是一当前子节点为根的子树产生的

 */

     for(int i = ; i < G[node].size(); i++){

         int v = G[node][i];

         for(int j = cnt[node]; j >= ; j--){

             for(int t = ; t<j && t<=cnt[v]; t++){

                 dp[node][j] = max(dp[node][j], dp[node][j-t]+dp[v][t]);

             }

         }

     }

     ans = max(ans, dp[node][k]);

     return cnt[node];

 }

 int main()

 {

     freopen("in.txt", "r", stdin);

     int n;

     while(scanf("%d%d",&n, &k) != EOF){

         mst(dp, );  ans = ;

         for(int i=; i<maxn; i++){

             G[i].clear();

         }

         for(int i=; i<n; i++){

             scanf("%d", &weight[i]);

         }

         int a, b;

         for(int i = ; i < n; i++){

             scanf("%d%d", &a, &b);

             G[a].push_back(b);

             G[b].push_back(a);

         }

         dfs(, -);

         printf("%d\n", ans);

     }

     return ;

 }

E - Cell Phone Network

题意：给n[1,10000]个点，n-1条边，树形结构，从n个点中取尽量少的点构成一个集合，使剩下所有点都能与这个集合中的部分点相连。

(这个概念叫最小支配集)

dp[u][]：以点u为根的被染色的点的个数

dp[u][0]:u不染色，父节点染色覆盖u        min(1, 2)u不染色，不能覆盖子节点v，故要不v染色覆盖自己，要不v被v染色的子节点覆盖

dp[u][1]:u不染色，子节点存在被染色的覆盖u                  min(1,2)u不染色，所以子节点v不存在被染色的父亲；若所有v均不染色，此时u未被覆盖，故需要有一个v来染色，选择min(dp[v][2]-dp[v][1])即可。

dp[u][2]:u染色                      min(0,1,2)+1 子节点v染不染色都可以；自己染色故需+1

 /*

  * poj3659

  * 最小支配集:从所有顶点中取尽量少的点组成一个集合，

  *            使剩下的所有点都与取出来的所有点相连。

  * dp[u]:以点u为根的被染色的点的个数

  *

  * dp[u][0]:u不染色，父节点染色覆盖u

  * dp[u][1]:u不染色，子节点存在被染色的覆盖u

  * dp[u][2]:u染色

 */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 const int maxn = ;

 vector<int> G[maxn];

 int dp[maxn][], n;

 void dfs(int u, int f){

     //叶子结点

     if(G[u].size()== && G[u][]==f){

         dp[u][] = ;

         dp[u][] = inf;

         dp[u][] = ;

         return;

     }

     int mini = inf, flag = ;

     for(int i=; i<G[u].size(); i++){

         int v = G[u][i];

         if(v == f) continue;

         dfs(v, u);

         dp[u][] += min(dp[v][], dp[v][]);

         dp[u][] += min(min(dp[v][], dp[v][]), dp[v][]);

         if(dp[v][] < dp[v][]){

             dp[u][] += dp[v][];

             mini = min(mini, (dp[v][] - dp[v][]));

         }else{

             flag = ;

             dp[u][] += dp[v][];

         } 

     }

     dp[u][]++;   //u点需要染色

     if(flag){

 /*

  * 如果所有子节点dp[v][1]<dp[v][2],则所有子节点点不放,这时必须有一个孩子结点放才可以保证

  * u被覆盖

 */

         dp[u][] += mini;

     }

 }

 int main(){

     //freopen("in.txt", "r", stdin);

     int n; scanf("%d", &n);

     for(int i=; i<=n; i++)G[i].clear();

     for(int i=; i<n; i++){

         int a, b; scanf("%d%d", &a, &b);

         G[a].push_back(b); G[b].push_back(a);

     }

     dfs(, -);

     printf("%d\n", min(dp[][], dp[][]));

     //1是根,无父节点

     return ;

 }

F - Computer

题意：一棵边带权值的树，求每个点在树上的最远距离。

参考blog

1、dp：计算点v在树上的最远距离，通过dfs()寻找。v通过v的子树可以找到最远距离，v也可以通过v的父节点找到最远距离。通过子树找，向下遍历更新即可(即向下寻找)。通过父节点找，需要知道父节点的最远距离，父节点可以通过找自己的父节点获得最远距离(即一直向上寻找)，也可以通过寻找子树获得最远距离(但不能包含以v为根的子树(否则会重复))(即先向上后向下寻找)，这里就需要结点的次远距离(即该距离是不包含结点最远距离上的第一个结点的最远距离，故称为次远距离)。

 /*

  * hdu2196

  *

 */

 #include <bits/stdc++.h>

 #define LL long long

 using namespace std;

 const int maxn =  1e4+;

 struct edge{

     int to, val;

     edge(int a, int b) : to(a), val(b) {}

 };

 vector<edge> G[maxn];

 int dp[][maxn], id[maxn];

 //树只有一个父亲，会有多个儿子

 //id[v]: v在v的子树中可以得到的最大距离，所经过的第一个孩子结点

 //dp[v][0]: v在v的所有子树中获得的最长距离

 //dp[v][1]: v的孩子的第二长距离

 //dp[v][2]: v通过父亲获得的最长距离

 void dfs1(int x, int f){

     for(int i=; i<G[x].size(); i++){

         int to = G[x][i].to, w = G[x][i].val;

         if(to == f) continue;

         dfs1(to, x);

         if(dp[][x] < dp[][to] + w){

             dp[][x] = dp[][to] + w;

             id[x] = to;   //记录点x的最大距离经过的第一个孩子结点

         }

     }

     for(int i=; i<G[x].size(); i++){

         int to = G[x][i].to, w = G[x][i].val;

         if(to == f) continue;

         if(id[x] == to) continue;  //找次大的

         dp[][x] = max(dp[][x], w + dp[][to]);

     }

 }

 void dfs2(int x, int f){

     for(int i=; i<G[x].size(); i++){

         int to = G[x][i].to, w = G[x][i].val;

         if(to == f) continue;

         if(to == id[x]){

             dp[][to] = max(dp[][x], dp[][x]) + w;

             //to是x的孩子:to的最大距离是 x不经过to的最大距离(即次大距离)[向下的]和

             //x向上的最大距离  的最大值 + dist(x,to) (画图理解)

             //这里的转移也是dp[v][1]和id[x]存在的意义

         }else{

             dp[][to] = max(dp[][x], dp[][x]) + w;

             //to不是x最大距离经过的点

             //则to的最大距离是dist(x,to)和x向上或向下的最大距离的最大值

         }

         dfs2(to, x);

         //0和1子树的信息可以直接用,2也是步步更新,一直到最优

     }

 }

 int main(){

     //freopen("in.txt", "r", stdin);

     int n;

     while(scanf("%d", &n) != EOF){

         memset(dp, , sizeof(dp));

         for(int i=;i<=n;i++)G[i].clear();

         for(int i=; i<=n; i++){

             int a, b; scanf("%d%d", &a, &b);

             G[i].push_back(edge(a, b));

             G[a].push_back(edge(i, b));

         }

         dfs1(, -);

         dfs2(, -);

         for(int i=; i<=n; i++){

             printf("%d\n", max(dp[][i], dp[][i]));

         }

     }

     return ;

 }

2、用树的直径求解：3次dfs()。前两次求树的直径，后两次求得所有点距离直径端点的最远距离。

 /*

  * 树中的最长路径，

 */

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = 1e4+;

 struct edge{

     int to, val;

     edge(int a, int b) : to(a), val(b) {}

 };

 vector<edge> G[maxn];

 int dp[maxn], max_len, s;

 void dfs(int x, int f, int len){

 //len:起点到当前点的距离

     if(max_len <= len){

         s = x;

         max_len = len;

     }

     for(int i=; i<G[x].size(); i++){

         int to = G[x][i].to, w = G[x][i].val;

         if(f == to) continue;

         dfs(to, x, len+w);

         dp[to] = max(dp[to], len+w);

         //更新起点到当前点的距离

     }

 }

 int main(){

     freopen("in.txt", "r", stdin);

     int n;

     while(scanf("%d", &n) != EOF){

         memset(dp, , sizeof(dp));

         for(int i=;i<=n;i++) G[i].clear();

         for(int i=; i<=n; i++){

             int a,b; scanf("%d%d",&a, &b);

             G[i].push_back(edge(a, b));

             G[a].push_back(edge(i, b));

         }

         s=, max_len=;

         dfs(, -, );

         dfs(s, -, );

         dfs(s, -, );

         for(int i=; i<=n; i++){

             printf("%d\n", dp[i]);

         }

     }

     return ;

 }

hdu6446 Tree and Permutation

题意：给一个n（1e5）个点，n-1条边的树，按结点进行全排列，对每个全排列，求其第一个结点到其余结点的距离之和，再求全排列的和。

每条边单独计算，边E左边x个点，右边(n-x)个点。则在全排列n!中，每种排列有n-1段，每段的贡献是 *x*(n-x)*(n-)!*w ，一共n-1段，则贡献为 *x*(n-x)*(n-)!*w 。一共n-1条边，sum()即可

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = 1e5+;

 #define LL long long

 const LL mod = 1e9+;

 struct edge{

     int to, val;

     edge(int a, int b) : to(a), val(b) {}

 };

 vector<edge> G[maxn];

 LL d[maxn], w[maxn], node[maxn];

 //node[x]: f-->x这条边在x一边的点的个数

 //w[x]: f-->x这条边的权值

 //d[i]: i!

 void get_d(){

     d[] = ;

     for(int i=; i<maxn; i++){

         d[i] = (1LL * i * d[i-]) % mod;

     }

 }

 LL dfs(int x, int f){

     LL ans = ;

     for(int i=; i<G[x].size(); i++){

         int v = G[x][i].to;

         if(v == f){

             w[x] = (LL)G[x][i].val;  //将边f---->x的权值存在当前结点w[x]

         }else{

             ans += dfs(v, x); //统计结点数

         }

     }

     if(f!=- && G[x].size()==){ //叶子结点

         return node[x] = ;   //叶子结点一边的点数为1

     }

     return node[x] = ans;

 }

 int main(){

     //freopen("in.txt", "r", stdin);

     get_d();

     int n;

     while(scanf("%d", &n) != EOF){

         for(int i=; i<=n; i++) G[i].clear();

         for(int i=; i<n; i++){

             int x, y, z;  scanf("%d%d%d", &x, &y, &z);

             G[x].push_back(edge(y, z));

             G[y].push_back(edge(x, z));

         }

         dfs(, -);

         LL ans = ;

         //ans = sum(2*x*(n-x)*(n-1)!*w[i]) = (n-1)!*sum(2*x*(n-x)*w[i])

         for(int i=; i<=n; i++){

             ans  = (ans + ( ((*node[i]*(n-node[i]))%mod) * w[i])%mod )%mod;

         }

         printf("%lld\n", (ans * d[n-])%mod);

     }

     return ;

 }

UVA 10859 Placing Lampposts（训练指南P70）

题意：n个点m条边的无向无环图。在尽量少的结点上放灯，使所有边都被照亮，灯的总数最小的前提下，被两盏灯同时照亮的边数尽量大。

与E求最小支配集相似，多了同时照亮的边数尽量大的目标。

下面两个关于这题的思路很nice：

多目标优化问题这里有一个思路是 x=Ma+c，M是“c的最大理论值与a的最小理论值之差”还要大的数。

还需要进行目标转换：边数一定，被两盏灯同时照亮的边数比较大，则被一盏灯照亮的边数尽量小。

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 vector<int> G[maxn];

 int d[maxn][], n, m;

 //d[i][j]: i的父节点是否放灯的值为j;  d[i][j]:以i为根的最小x值

 bool vis[maxn][];

 int dfs(int i, int j, int f){

     int &ans = d[i][j];

     if(vis[i][j]) return ans;

     vis[i][j] = true;

     ans = ;   //i结点放灯,权重很大

     for(int k=; k<G[i].size(); k++){

         if(G[i][k] == f) continue;

         ans += dfs(G[i][k], , i);

     }

     if(j== && f>=){

     //因为i的父节点没放灯，所以这是被一盏灯照亮

         ans++;

     }

     if(j || f<){        //i是根或i的父亲放灯,i可以不放灯

         int sum = ;

         for(int k=; k<G[i].size(); k++){

             if(G[i][k] == f) continue;

             sum += dfs(G[i][k], , i);

         }

         if(f >= ) sum++;

         ans = min(ans, sum);

     }

     return ans;

 }

 int main(){

     //freopen("in.txt", "r", stdin);

     int t;

     scanf("%d", &t);

     while(t--){

         int n, m;

         scanf("%d%d", &n, &m);

         for(int i=; i<=n; i++)G[i].clear();

         for(int i=; i<m; i++){

             int x, y;

             scanf("%d%d", &x, &y);

             G[x].push_back(y);

             G[y].push_back(x);

         }

         memset(vis, , sizeof(vis));

         int ans = ;

         for(int i=; i<n; i++){

             if(!vis[i][]){

                 ans += dfs(i, , -);

             }

         }

         printf("%d %d %d\n", ans/, m-ans%, ans%);

     }

     return ;

 }
 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int M = ;

 vector<int> G[maxn];

 int dp[maxn][];

 bool vis[maxn];

 void dfs(int x){

     vis[x] = true;

     dp[x][] = ; dp[x][] = M;

     for(int i=; i<G[x].size(); i++){

         int v = G[x][i];

         if(vis[v]) continue;

         dfs(v);

         dp[x][] += dp[v][] + ;

         dp[x][] += min(dp[v][], dp[v][]+);

     }

 }

 int main(){

     //freopen("in.txt", "r", stdin);

     int t; scanf("%d", &t);

     while(t--){

         int n, m; scanf("%d%d", &n, &m);

         for(int i=;i<=n;i++)G[i].clear();

         for(int i=; i<m; i++){

             int a, b;scanf("%d%d", &a, &b);

             G[a].push_back(b); G[b].push_back(a);

         }

         memset(vis, , sizeof(vis));

         int ans = ;

         for(int i=; i<n; i++){

             if(vis[i]) continue;

             dfs(i);

             ans += min(dp[i][], dp[i][]);

         }

         printf("%d %d %d\n", ans/M, m-ans%M, ans%M);

     }

     return ;

 }

最新文章

  1. IaaS/PaaS/SaaS
  2. 解决chrome在docky上的图标模糊或不能锁定的问题
  3. 分享Kali Linux 2016.2第49周镜像文件
  4. STM32学习笔记(六) SysTick系统时钟滴答实验(stm32中断入门)
  5. (MST) HDOJ 1102 Constructing Roads
  6. 邮箱mail 发送类 ASP.NET C#
  7. BZOJ 2287: 【POJ Challenge】消失之物( 背包dp )
  8. crm创建基于fetch自己的自定义报告
  9. Codeforces Round #366 (Div. 2)_B. Spider Man
  10. node服务成长之路
  11. EmpyoyeeManger_1.0
  12. Iframe父子窗口之间的跨域事件调用和传值
  13. Python基础学习参考（四）：条件与循环
  14. 自己动手实现一个Android Studio插件
  15. [深度应用]&#183;DC竞赛轴承故障检测开源Baseline（基于Keras 1D卷积 val_acc:0.99780）
  16. CodeForces 510C Fox And Names (拓扑排序)
  17. 如何下载 Google Play 应用的apk
  18. 《ERP系统》客户信用及风控代码
  19. Java知多少（101）图像缓冲技术
  20. 【HAOI2011】problem a

热门文章

  1. Java Part 001( 03_01_数据类型和运算符 )
  2. sql server 很好的基础练习 &lt;学生表-老师表-课程表-选课表&gt;
  3. 001_git: 版本控制软件
  4. java.lang.OutOfMemoryError:PermGen space tomcat7 内存溢出
  5. Mac 安装软件时,提示已损坏解决
  6. @ControllerAdvice 和 @ExceptionHandler
  7. OpenJudge 1.5.36:计算多项式的值
  8. PHP开发高可用高安全App后端☆
  9. zabbix（x）
  10. 2018-2019-2 网络对抗技术 20165311 Exp 8 Web基础