P1352 没有上司的舞会#include bits/stdc.h using namespace std; int n, r[6010], l, k, root, fa[6010], f[6010][2], ans; //k是l的上司 vectorint son[6010]; void dp(int x) { f[x][0]0; //x不参加舞会 f[x][1]r[x]; //x参加舞会 for(int i0; ison[x].size(); i){ int yson[x][i]; dp(y); f[x][0]max(f[y][0], f[y][1]); f[x][1]f[y][0]; } } int main() { scanf(%d, n); for(int i1; in; i){ scanf(%d, r[i]); } for(int i1; in-1; i){ scanf(%d %d, l, k); //k是l的上司 fa[l]k; //k是父亲结点 son[k].push_back(l); //l是儿子结点 } //找根节点 for(int i1; in; i){ if(!fa[i]){ rooti; break; } } dp(root); ansmax(f[root][0], f[root][1]); printf(%d, ans); return 0; }P2585 [ZJOI2006] 三色二叉树#include iostream #include algorithm #include string.h using namespace std; string s; int n, tree[500010][3], cnt, dp_max[500010][3], dp_min[500010][3]; void build() { cnt; int ucnt; if(s[u-1]2){ tree[u][1]cnt1; build(); tree[u][2]cnt1; build(); } else if(s[u-1]1){ tree[u][1]cnt1; build(); } else if(s[u-1]0){ return; } } void dfs(int u) { //该节点为空则直接return if(u0){ return; } //如果是叶子节点 if(tree[u][1]0){ //节点u染绿色的情况下以节点u为根的子树中最多和最少的绿色节点数 dp_max[u][1]1; dp_min[u][1]1; //节点u不染绿色的情况下以节点u为根的子树中最多和最少的绿色节点数 dp_max[u][0]0; dp_min[u][0]0; } else if(tree[u][1]!0){ int ltree[u][1]; int rtree[u][2]; dfs(l); dfs(r); //节点u染绿色的情况下以节点u为根的子树中最多和最少的绿色节点数 //u染绿色的情况下两个子节点都不能染绿色 dp_max[u][1]1dp_max[l][0]dp_max[r][0]; dp_min[u][1]1dp_min[l][0]dp_min[r][0]; //节点u不染绿色的情况下以节点u为根的子树中最多和最少的绿色节点数 //u不染绿色两个字节点就必须有一个染绿色一个不染绿色 dp_max[u][0]max(dp_max[l][1]dp_max[r][0], dp_max[l][0]dp_max[r][1]); dp_min[u][0]min(dp_min[l][1]dp_min[r][0], dp_min[l][0]dp_min[r][1]); } } int main() { cin s; //建树 build(); ns.size(); // for(int i1; in; i){ // cout i tree[i][1] tree[i][2] endl; // } dfs(1); //1号根节点不染绿色和染绿色分别求最大值和最小值 cout max(dp_max[1][0], dp_max[1][1]) min(dp_min[1][0], dp_min[1][1]) endl; return 0; }P2015 二叉苹果树树上背包#include bits/stdc.h using namespace std; int n, q, dp[110][110], tot, head[110], x, y, z; bool vis[110]; struct node { int to, dis, nex; }e[210]; void add(int u, int v, int w) { tot; e[tot].tov; e[tot].disw; e[tot].nexhead[u]; head[u]tot; } //从u点出发, 求出dp[u][1]~dp[u][q] void dfs(int u){ vis[u]true; for(int ihead[u]; i; ie[i].nex){ int ve[i].to; int we[i].dis; if(vis[v]){ //如果已经考虑过点v, 则跳过 continue; } //从v点出发, 求出dp[v][1]~dp[v][q] dfs(v); for(int jq; j1; --j){ //01背包, 背包容量倒序 //v节点往出散的树枝数量, 因为u,v相连, 所以v最多只能往出散j-1条树枝, //如果v带0条树枝, 相当于不选节点v for(int kj-1; k0; --k){ //k表示点v往出散的树枝数量, 当k为0时, v不往出散树枝 //v往出散k条树枝, 则u只能往出散j-k-1条, 留一条给uv dp[u][j]max(dp[u][j], dp[v][k]dp[u][j-k-1]w); } } } } int main() { scanf(%d %d, n, q); for(int i1; in; i){ scanf(%d %d %d, x, y, z); add(x, y, z); add(y, x, z); } //从根1出发, 求出dp[1][1]~dp[1][q] dfs(1); printf(%d, dp[1][q]); return 0; }第一个点5 3 1 2 0 1 5 1 5 3 100 5 4 1第一个点102P1273 有线电视网P1040 [NOIP2003 提高组] 加分二叉树P1122 最大子树和#include bits/stdc.h using namespace std; int n, a, b, beauty[17000], dp[17000], tot, head[17000], ans-2e9; //不能全剪掉 bool vis[17000]; struct node { int to, nex; }e[40000]; void add(int u, int v) { tot; e[tot].tov; e[tot].nexhead[u]; head[u]tot; } //以点u为根节点的树中, 最大的美丽指数 void dfs(int u) { vis[u]true; //每次在dfs刚开始就标记 dp[u]beauty[u]; //以u为根, 必须选u //枚举所有的儿子节点 for(int ihead[u]; i; ie[i].nex){ int ve[i].to; if(vis[v]){ //如果访问过, 直接跳过 continue; } dfs(v); //在以点v为根节点的树中, 找最大的美丽指数 if(dp[v]0){ //如果以点v为根节点的树中, 有大于0的美丽指数, 就加上这一分支 dp[u]dp[v]; } } } int main() { scanf(%d, n); for(int i1; in; i){ scanf(%d, beauty[i]); } for(int i1; in; i){ scanf(%d %d, a, b); add(a, b); add(b, a); } dfs(1); for(int i1; in; i){ ansmax(ans, dp[i]); } printf(%d, ans); return 0; }U81904 【模板】树的直径#include bits/stdc.h #define int long long using namespace std; int n, m, uu, vv, ww, head[500010], tot, ans; bool vis[500010]; struct node { int to, dis, nex; }e[1000010]; void add(int u, int v, int w) { tot; e[tot].tov; e[tot].disw; e[tot].nexhead[u]; head[u]tot; } //从u出发找离它最远的点的距离, 和第二远的距离 int dfs(int u) { vis[u]true; int dist0, d10, d20; for(int ihead[u]; i; ie[i].nex){ int ve[i].to; if(vis[v]){ //如果已经基于点v dfs过了 continue; } int we[i].dis; int ddfs(v)w; distmax(dist, d); //打擂台, 找距离点u最远的点, 并更新最远距离 if(dd1){ d2d1; d1d; } else if(dd2){ d2d; } cout d1 asd d2 endl; } ansmax(ans, d1d2); return dist; } signed main() { scanf(%lld, n); for(int i1; in; i){ scanf(%lld %lld %lld, uu, vv, ww); add(uu, vv, ww); add(vv, uu, ww); } //找出每个点出发, 离它最远的点的距离加上第二远点的距离就是答案 dfs(1); printf(%lld, ans); return 0; }T95371 约数变换nlogn求约数#include bits/stdc.h using namespace std; int n, ans, tot, head[50010], sum[50010]; bool root[50010]; struct node { int to, nex; }e[50010]; void add(int u, int v) { tot; e[tot].tov; e[tot].nexhead[u]; head[u]tot; } int dfs(int u) { //从u出发的最长路径长度d1, 第二长路径长度d2 int d10, d20; for(int ihead[u]; i; ie[i].nex){ int ve[i].to; int ddfs(v)1; if(dd1){ d2d1; d1d; } else if(dd2){ d2d; } } ansmax(ans, d1d2); return d1; } int main() { scanf(%d, n); for(int i1; in; i){ for(int j2; jn/i; j){ sum[i*j]i; } } //i从2开始, 因为1的约数和为0, 题目要求所有的数都是正数 for(int i2; in; i){ if(sum[i]i){ add(sum[i], i); root[i]true; } } //树根是可以从1开始枚举的 for(int i1; in; i){ if(!root[i]){ dfs(i); } } printf(%d, ans); return 0; }nsqrt(n)求约数#include bits/stdc.h using namespace std; int n, ans, tot, head[50010], sum[50010]; bool root[50010]; struct node { int to, nex; }e[50010]; void add(int u, int v) { tot; e[tot].tov; e[tot].nexhead[u]; head[u]tot; } int dfs(int u) { //从u出发的最长路径长度d1, 第二长路径长度d2 int d10, d20; for(int ihead[u]; i; ie[i].nex){ int ve[i].to; int ddfs(v)1; if(dd1){ d2d1; d1d; } else if(dd2){ d2d; } } ansmax(ans, d1d2); return d1; } int main() { scanf(%d, n); for(int i1; in; i){ for(int j1; jsqrt(i); j){ if(i%j0){ sum[i]ji/j; if(j*ji){ sum[i]-j; } } } sum[i]-i; } //i从2开始, 因为1的约数和为0, 题目要求所有的数都是正数 for(int i2; in; i){ if(sum[i]i){ add(sum[i], i); root[i]true; } } //树根是可以从1开始枚举的 for(int i1; in; i){ if(!root[i]){ dfs(i); } } printf(%d, ans); return 0; }P2014 [CTSC1997] 选课#include bits/stdc.h using namespace std; int n, m, dp[310][310], tot, head[310], kk, ss; bool vis[310]; struct node { int to, dis, nex; }e[310]; void add(int u, int v) { tot; e[tot].tov; e[tot].nexhead[u]; head[u]tot; } //从u点出发, 求出dp[u][1]~dp[u][q] void dfs(int u){ vis[u]true; for(int ihead[u]; i; ie[i].nex){ int ve[i].to; if(vis[v]){ //如果已经考虑过点v, 则跳过 continue; } //从v点出发, 求出dp[v][1]~dp[v][m] dfs(v); for(int jm; j1; --j){ //01背包, 背包容量倒序 //k表示以v节点为根的选课数量, 因为u必须选, 所以以v为根最多只能选j-1门课, //如果以v为根选0门课, 相当于不选v这门课 for(int k0; kj-1; k){ //k表示以v为根的选课数量, 当k为0时, 不选v这门课 //以v为根选k门课, 则以u为根到截止到v时(没有选v)只能选j-k门课 dp[u][j]max(dp[u][j], dp[v][k]dp[u][j-k]); } } } } int main() { scanf(%d %d, n, m); for(int i1; in; i){ scanf(%d %d, kk, ss); dp[i][1]ss; add(kk, i); //0作为超级根, 将森林变为树 } m; //因为多选了一门0号虚拟课程 //从根0出发, 求出dp[0][1]~dp[0][m] dfs(0); printf(%d, dp[0][m]); return 0; }P3174 [HAOI2009] 毛毛虫#include iostream #include algorithm #include vector using namespace std; //dp[u]表示以u为起点在它的子树中找一条链, 所能形成的毛毛虫的最大值 int n, m, a, b, dp[300010], id, cnt, mx; vectorint asd[300010]; void dfs(int u, int fa) { int mx10, mx20; for(int i0; iasd[u].size(); i){ int vasd[u][i]; if(v!fa){ dfs(v, u); dp[u]max(dp[u], dp[v]); //如果比最大儿子还要大 if(dp[v]mx1){ mx2mx1; //原来的最大儿子退居二线 mx1dp[v]; //dp[v]变成最大的 } else if(dp[v]mx2){ //如果比二儿子大 mx2dp[v]; } } } if(asd[u].size()1){ dp[u]1; mxmax(mx, dp[u]); } else{ dp[u]asd[u].size()-1; mxmax(mx, int(mx1mx2asd[u].size()-1)); } } int main() { scanf(%d %d, n, m); for(int i1; im; i){ scanf(%d %d, a, b); asd[a].push_back(b); asd[b].push_back(a); } dfs(1, 0); // for(int i1; in; i){ // cout i dp[i] endl; // } printf(%d\n, mx); return 0; }P3047 [USACO12FEB]Nearby Cows GP3698 [CQOI2017]小Q的棋盘P5658 [CSP-S2019] 括号树P2607 [ZJOI2008] 骑士P3177 [HAOI2015] 树上染色P4395 [BOI2003]Gem 气垫车P4516 [JSOI2018] 潜入行动P2700 逐个击破
树形dp经典题目
P1352 没有上司的舞会#include bits/stdc.h using namespace std; int n, r[6010], l, k, root, fa[6010], f[6010][2], ans; //k是l的上司 vectorint son[6010]; void dp(int x) { f[x][0]0; //x不参加舞会 f[x][1]r[x]; //x参加舞会 for(int i0; ison[x].size(); i){ int yson[x][i]; dp(y); f[x][0]max(f[y][0], f[y][1]); f[x][1]f[y][0]; } } int main() { scanf(%d, n); for(int i1; in; i){ scanf(%d, r[i]); } for(int i1; in-1; i){ scanf(%d %d, l, k); //k是l的上司 fa[l]k; //k是父亲结点 son[k].push_back(l); //l是儿子结点 } //找根节点 for(int i1; in; i){ if(!fa[i]){ rooti; break; } } dp(root); ansmax(f[root][0], f[root][1]); printf(%d, ans); return 0; }P2585 [ZJOI2006] 三色二叉树#include iostream #include algorithm #include string.h using namespace std; string s; int n, tree[500010][3], cnt, dp_max[500010][3], dp_min[500010][3]; void build() { cnt; int ucnt; if(s[u-1]2){ tree[u][1]cnt1; build(); tree[u][2]cnt1; build(); } else if(s[u-1]1){ tree[u][1]cnt1; build(); } else if(s[u-1]0){ return; } } void dfs(int u) { //该节点为空则直接return if(u0){ return; } //如果是叶子节点 if(tree[u][1]0){ //节点u染绿色的情况下以节点u为根的子树中最多和最少的绿色节点数 dp_max[u][1]1; dp_min[u][1]1; //节点u不染绿色的情况下以节点u为根的子树中最多和最少的绿色节点数 dp_max[u][0]0; dp_min[u][0]0; } else if(tree[u][1]!0){ int ltree[u][1]; int rtree[u][2]; dfs(l); dfs(r); //节点u染绿色的情况下以节点u为根的子树中最多和最少的绿色节点数 //u染绿色的情况下两个子节点都不能染绿色 dp_max[u][1]1dp_max[l][0]dp_max[r][0]; dp_min[u][1]1dp_min[l][0]dp_min[r][0]; //节点u不染绿色的情况下以节点u为根的子树中最多和最少的绿色节点数 //u不染绿色两个字节点就必须有一个染绿色一个不染绿色 dp_max[u][0]max(dp_max[l][1]dp_max[r][0], dp_max[l][0]dp_max[r][1]); dp_min[u][0]min(dp_min[l][1]dp_min[r][0], dp_min[l][0]dp_min[r][1]); } } int main() { cin s; //建树 build(); ns.size(); // for(int i1; in; i){ // cout i tree[i][1] tree[i][2] endl; // } dfs(1); //1号根节点不染绿色和染绿色分别求最大值和最小值 cout max(dp_max[1][0], dp_max[1][1]) min(dp_min[1][0], dp_min[1][1]) endl; return 0; }P2015 二叉苹果树树上背包#include bits/stdc.h using namespace std; int n, q, dp[110][110], tot, head[110], x, y, z; bool vis[110]; struct node { int to, dis, nex; }e[210]; void add(int u, int v, int w) { tot; e[tot].tov; e[tot].disw; e[tot].nexhead[u]; head[u]tot; } //从u点出发, 求出dp[u][1]~dp[u][q] void dfs(int u){ vis[u]true; for(int ihead[u]; i; ie[i].nex){ int ve[i].to; int we[i].dis; if(vis[v]){ //如果已经考虑过点v, 则跳过 continue; } //从v点出发, 求出dp[v][1]~dp[v][q] dfs(v); for(int jq; j1; --j){ //01背包, 背包容量倒序 //v节点往出散的树枝数量, 因为u,v相连, 所以v最多只能往出散j-1条树枝, //如果v带0条树枝, 相当于不选节点v for(int kj-1; k0; --k){ //k表示点v往出散的树枝数量, 当k为0时, v不往出散树枝 //v往出散k条树枝, 则u只能往出散j-k-1条, 留一条给uv dp[u][j]max(dp[u][j], dp[v][k]dp[u][j-k-1]w); } } } } int main() { scanf(%d %d, n, q); for(int i1; in; i){ scanf(%d %d %d, x, y, z); add(x, y, z); add(y, x, z); } //从根1出发, 求出dp[1][1]~dp[1][q] dfs(1); printf(%d, dp[1][q]); return 0; }第一个点5 3 1 2 0 1 5 1 5 3 100 5 4 1第一个点102P1273 有线电视网P1040 [NOIP2003 提高组] 加分二叉树P1122 最大子树和#include bits/stdc.h using namespace std; int n, a, b, beauty[17000], dp[17000], tot, head[17000], ans-2e9; //不能全剪掉 bool vis[17000]; struct node { int to, nex; }e[40000]; void add(int u, int v) { tot; e[tot].tov; e[tot].nexhead[u]; head[u]tot; } //以点u为根节点的树中, 最大的美丽指数 void dfs(int u) { vis[u]true; //每次在dfs刚开始就标记 dp[u]beauty[u]; //以u为根, 必须选u //枚举所有的儿子节点 for(int ihead[u]; i; ie[i].nex){ int ve[i].to; if(vis[v]){ //如果访问过, 直接跳过 continue; } dfs(v); //在以点v为根节点的树中, 找最大的美丽指数 if(dp[v]0){ //如果以点v为根节点的树中, 有大于0的美丽指数, 就加上这一分支 dp[u]dp[v]; } } } int main() { scanf(%d, n); for(int i1; in; i){ scanf(%d, beauty[i]); } for(int i1; in; i){ scanf(%d %d, a, b); add(a, b); add(b, a); } dfs(1); for(int i1; in; i){ ansmax(ans, dp[i]); } printf(%d, ans); return 0; }U81904 【模板】树的直径#include bits/stdc.h #define int long long using namespace std; int n, m, uu, vv, ww, head[500010], tot, ans; bool vis[500010]; struct node { int to, dis, nex; }e[1000010]; void add(int u, int v, int w) { tot; e[tot].tov; e[tot].disw; e[tot].nexhead[u]; head[u]tot; } //从u出发找离它最远的点的距离, 和第二远的距离 int dfs(int u) { vis[u]true; int dist0, d10, d20; for(int ihead[u]; i; ie[i].nex){ int ve[i].to; if(vis[v]){ //如果已经基于点v dfs过了 continue; } int we[i].dis; int ddfs(v)w; distmax(dist, d); //打擂台, 找距离点u最远的点, 并更新最远距离 if(dd1){ d2d1; d1d; } else if(dd2){ d2d; } cout d1 asd d2 endl; } ansmax(ans, d1d2); return dist; } signed main() { scanf(%lld, n); for(int i1; in; i){ scanf(%lld %lld %lld, uu, vv, ww); add(uu, vv, ww); add(vv, uu, ww); } //找出每个点出发, 离它最远的点的距离加上第二远点的距离就是答案 dfs(1); printf(%lld, ans); return 0; }T95371 约数变换nlogn求约数#include bits/stdc.h using namespace std; int n, ans, tot, head[50010], sum[50010]; bool root[50010]; struct node { int to, nex; }e[50010]; void add(int u, int v) { tot; e[tot].tov; e[tot].nexhead[u]; head[u]tot; } int dfs(int u) { //从u出发的最长路径长度d1, 第二长路径长度d2 int d10, d20; for(int ihead[u]; i; ie[i].nex){ int ve[i].to; int ddfs(v)1; if(dd1){ d2d1; d1d; } else if(dd2){ d2d; } } ansmax(ans, d1d2); return d1; } int main() { scanf(%d, n); for(int i1; in; i){ for(int j2; jn/i; j){ sum[i*j]i; } } //i从2开始, 因为1的约数和为0, 题目要求所有的数都是正数 for(int i2; in; i){ if(sum[i]i){ add(sum[i], i); root[i]true; } } //树根是可以从1开始枚举的 for(int i1; in; i){ if(!root[i]){ dfs(i); } } printf(%d, ans); return 0; }nsqrt(n)求约数#include bits/stdc.h using namespace std; int n, ans, tot, head[50010], sum[50010]; bool root[50010]; struct node { int to, nex; }e[50010]; void add(int u, int v) { tot; e[tot].tov; e[tot].nexhead[u]; head[u]tot; } int dfs(int u) { //从u出发的最长路径长度d1, 第二长路径长度d2 int d10, d20; for(int ihead[u]; i; ie[i].nex){ int ve[i].to; int ddfs(v)1; if(dd1){ d2d1; d1d; } else if(dd2){ d2d; } } ansmax(ans, d1d2); return d1; } int main() { scanf(%d, n); for(int i1; in; i){ for(int j1; jsqrt(i); j){ if(i%j0){ sum[i]ji/j; if(j*ji){ sum[i]-j; } } } sum[i]-i; } //i从2开始, 因为1的约数和为0, 题目要求所有的数都是正数 for(int i2; in; i){ if(sum[i]i){ add(sum[i], i); root[i]true; } } //树根是可以从1开始枚举的 for(int i1; in; i){ if(!root[i]){ dfs(i); } } printf(%d, ans); return 0; }P2014 [CTSC1997] 选课#include bits/stdc.h using namespace std; int n, m, dp[310][310], tot, head[310], kk, ss; bool vis[310]; struct node { int to, dis, nex; }e[310]; void add(int u, int v) { tot; e[tot].tov; e[tot].nexhead[u]; head[u]tot; } //从u点出发, 求出dp[u][1]~dp[u][q] void dfs(int u){ vis[u]true; for(int ihead[u]; i; ie[i].nex){ int ve[i].to; if(vis[v]){ //如果已经考虑过点v, 则跳过 continue; } //从v点出发, 求出dp[v][1]~dp[v][m] dfs(v); for(int jm; j1; --j){ //01背包, 背包容量倒序 //k表示以v节点为根的选课数量, 因为u必须选, 所以以v为根最多只能选j-1门课, //如果以v为根选0门课, 相当于不选v这门课 for(int k0; kj-1; k){ //k表示以v为根的选课数量, 当k为0时, 不选v这门课 //以v为根选k门课, 则以u为根到截止到v时(没有选v)只能选j-k门课 dp[u][j]max(dp[u][j], dp[v][k]dp[u][j-k]); } } } } int main() { scanf(%d %d, n, m); for(int i1; in; i){ scanf(%d %d, kk, ss); dp[i][1]ss; add(kk, i); //0作为超级根, 将森林变为树 } m; //因为多选了一门0号虚拟课程 //从根0出发, 求出dp[0][1]~dp[0][m] dfs(0); printf(%d, dp[0][m]); return 0; }P3174 [HAOI2009] 毛毛虫#include iostream #include algorithm #include vector using namespace std; //dp[u]表示以u为起点在它的子树中找一条链, 所能形成的毛毛虫的最大值 int n, m, a, b, dp[300010], id, cnt, mx; vectorint asd[300010]; void dfs(int u, int fa) { int mx10, mx20; for(int i0; iasd[u].size(); i){ int vasd[u][i]; if(v!fa){ dfs(v, u); dp[u]max(dp[u], dp[v]); //如果比最大儿子还要大 if(dp[v]mx1){ mx2mx1; //原来的最大儿子退居二线 mx1dp[v]; //dp[v]变成最大的 } else if(dp[v]mx2){ //如果比二儿子大 mx2dp[v]; } } } if(asd[u].size()1){ dp[u]1; mxmax(mx, dp[u]); } else{ dp[u]asd[u].size()-1; mxmax(mx, int(mx1mx2asd[u].size()-1)); } } int main() { scanf(%d %d, n, m); for(int i1; im; i){ scanf(%d %d, a, b); asd[a].push_back(b); asd[b].push_back(a); } dfs(1, 0); // for(int i1; in; i){ // cout i dp[i] endl; // } printf(%d\n, mx); return 0; }P3047 [USACO12FEB]Nearby Cows GP3698 [CQOI2017]小Q的棋盘P5658 [CSP-S2019] 括号树P2607 [ZJOI2008] 骑士P3177 [HAOI2015] 树上染色P4395 [BOI2003]Gem 气垫车P4516 [JSOI2018] 潜入行动P2700 逐个击破
