11.3 周二
上周的后面几天一直在刚一道题，没刚出来，我太菜了
今天再刚，再刚不出就看题解。
现在事情开始渐渐多起来了。
啊，看来题解还是没太懂
明天上午用来理解题解吧
这一道题卡了我一个星期了……
没事，想的过程中实力就在提升
11.4 周三
P1272 重建道路
这道题真的搞了我近一个星期
所以上一周最后几天和这一周前几天的学习笔记都没怎么写，因为我一直在写这道题
最后看了题解，发现的确还是自己太菜了，一些点我想不清楚
首先是定义状态很容易想到f[u][j]表示以u为根的树，保留j个节点删边
的最小值
我中间还尝试了用f[u][j]表示删j个边所有的最大节点个数，后来代码是写
对了，但这种做法是错的，并不能得出正确答案。
然后就是转移方程的问题
这里把节点数代表费用，删边数代表价值，看成一个物品，那么方程就是
f[u][j] = f[u][j-k] + f[v][k]
这是典型的树上分组背包
然后这时我们是没有考虑根与父亲连的边的，平时当作它没有这条边，只在
转移的时候考虑这条边
然后我就卡在这里了，卡了很久一直想不出来这条边到底该怎么处理
之后看了题解也发现这个点是这道题最难的地方
这条边的处理涉及到初始化的问题。
初始化是f[u][1] = out[i], out[i]表示出度。因为求最小值，其他全部设为最大值
这里学到了用memset(f, 0x3f, sizeof(f)) 这样全部初始化成1e9左右，这个数很好，
足够大，加起来也不会负溢出
这里初始化的时候u和v的节点已经删掉了，这里的删去会影响后面的转移
后面转移的时候，只要子树的子节点数大于一，那么这条边就要连上
删掉的时候就已经包括子节点数为0的情况。
既然连上，那么边数就要多一条，也就是删去的边数要少一条，所以转移方程是
f[u][j] = f[u][j-k] + f[v][k] - 1;
我觉得这里的核心是开始初始化的时候把边已经删去了，后面转移要-1,同时不用考虑
节点数为0的情况
最后是统计答案
这个树形dp的过程中，是本来只有一个父节点，然后子节点一个个加上了了，所以用sum
记录总节点数（不用开数组）
这里统计答案要注意，最好树形dp完再统计答案
因为我写成边dp边统计答案的时候，叶子节点连循环都不会开始，就不会统计叶子节点的情况，
导致露了一些答案
也就是说dp过程可能不会统计所有可能的答案，一些特殊情况的答案统计不到
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 200;
int f[MAXN][MAXN], out[MAXN], in[MAXN];
int ans, n, p, root;
vector<int> g[MAXN];int dfs(int u)
{int sum = 1;REP(i, 0, g[u].size()){int v = g[u][i]; sum += dfs(v);for(int j = sum; j >= 1; j--)_for(k, 1, j - 1)f[u][j] = min(f[u][j], f[u][j-k] + f[v][k] - 1);}return sum;
}int main()
{scanf("%d%d", &n, &p);_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);out[u]++; in[v]++;}memset(f, 0x3f, sizeof(f));_for(i, 1, n){if(!in[i]) root = i;f[i][1] = out[i];}ans = 1e9; dfs(root);_for(i, 1, n){if(i == root) ans = min(ans, f[i][p]);else ans = min(ans, f[i][p] + 1);}printf("%d\n", ans);return 0;
}
11.5 周四
今天开始刷cf
做了一下div2的题目
前两题思维题，不需要用什么算法
第三题应该是一些基础算法，我做的这次是贪心
第四题就更难一点，不确定能否做出来。
那道题让我想到了单调栈，
接下来几天复习单调栈已经做D题
以后比赛争取做出前四题