AT2304 Cleaning 题意 一个树上每个节点有一些石子，每次只能选取两个叶子节点并将路径间的所有点上的石子数量减1，问是否能将所有石子取完。 思路 设 \(f_x\) 表示从 \(x\) 节点向上的路径条数，\(s_x\) 为子节点的 \(f\) 值的和，则有： \[ a_x=\frac{s_x-f_x}{2}+f_x\\ f_x=2a_x-s_x \] 我们只需要保...

CF459E-DP 核心代码15行 思路 观察数据范围，我们建m层分层图跑最短路想到DP。 DP最大的特点就是无后效性。那么我们这一题哪个条件无后效性呢？ 发现DP值一定从边权小于当前点的位置转移而来。 这不就无后效性了？我们按边权将所有边排序即可。 然后，枚举边，将DP值记录到点上，每次用起始点的dp值加1更新到达点的dp值。最后输出dp值最大的即可。 然后，您会发现第一个...

CF494D Birthday 题意 一个1为根的带边权有根树，每次询问给定两个点 \(u,v\) 求 \(\sum_{x\in S(v)} d(u,x)^2-\sum_{x\not\in S(v)}d(u,x)^2\) 其中 \(d(u,v)\) 表示 \(u,v\) 简单路径长度， \(S(u)\) 表示 \(u\) 的子树内点的集合。 思路 考虑 \(u\) 在 \(v\)...

P1040 加分二叉树 \(n\) 很小，可以树形 dp 或者区间 dp 。 设 f[i][j] 为从 \(i\) 到 \(j\) 的最大加分值，则有 f[i][j]=max(f[i][k-1]*f[k+1][j]+f[k][k])。 有一个小技巧，将 f[i][i-1] 全部设置为 1，这样的话搜索到叶子就也可以按照通式 dp 了。 对于输出前序遍历（根，左树，右树）我们再...

洛谷P2014选课 一道树形DP题。 f[i][j] 表示i个点选j门课程的最大学分。 递推方程： 1234for(int a=n;a>0;a--)//总共选择多少 for(int b=0;b<a;b++)//分别选择多少(b,a-b) f[x][a]=max(f[x][a],f[x][a-b]+f[u][b]);//都不遍历0的原因是f[i][0]无...

P2491 消防/P1099 树网的核 双倍经验，双倍快乐。 题意 在一个树上选择一段总长度不超过\(s\)的链使所有点到该链距离的最大值最小。 输出这个最小的值。 做法 Define:以下\(s\)指链或链长。 证明一下\(s\)一定处于直径上。假设它不在直径上，一定存在直径的其中一个端点到\(s\)的距离大于现在所处支链的最大距离。所以\(s\)不在直径上一定不优。 ...

P4074 [WC2013]糖果公园 树上带修莫队 题意：树上每个点有一种糖果，求\(\sum_c\sum_{i=1}^{cnt_c}v_c*w_i\) 其中c为糖果种类，\(cnt_c\)其为出现次数。 思路 离线树上带修莫队。 先进行树上分块。分块内的询问按照出发点、终止点、询问id优先级依次递减排序。 对于树上莫队，其实就是在欧拉序上莫队。因为欧拉序的性质，即每个节点子树...

P4827 [国家集训队] Crash 的文明世界 题意 求出对于树上每个点 \(x\) 的 \(\sum_{u=1}^ndis(x,u)^k\)。所有边长为 1。 思路 根据斯特林反演： \[ m^n=\sum_{j=0}^n\begin{Bmatrix}n\\j\end{Bmatrix}C_m^jj! \] 可以得到： \[ \sum_{i=1}^n\sum_{j=0}...

P5658 括号树 NOIp2019 我是永远不会忘记我那天在考场上傻瞪着题啥都不会的心理阴影的…… 于是今天我克服心理阴影来写这道题。 树形结构 因为这是一个树，所有优秀的性质这个题都有。并且题目仅仅是问从1开始到所有点的答案，所以我们就可以依靠树的性质来做。 首先，对于一个节点，我们给它记录几个值： \(lst_i\)表示i的贡献（只是i的贡献，并不包括从根节点到i路径...

P6753 [BalticOI 2013 Day1] Ball Machine 题意 给你一个树，每次从根节点放一个求，如果其子节点有空这个球会向下滚，若有多个节点为空则找儿子中以子树内编号的最小值为优先级从小到大找第一个为空的位置滚。 有两种操作，第一种插入若干个球，输出最后一个球到的节点编号；第二种删除一个位置，此时若有可以向下滚的球那么这个球就会滚，输出有多少个球滚了。 保证...