传送门 先上一个结论，所有kkk个节点应该构成一棵树，形状是原树的直径连着一堆子树，其中直径只经过一遍，子树的所有边经过两次，走法就是从直径的一段走到另一端，但是中途会离开直径，到某个和当前节点相连的子树逛一圈再回到这个节点。 所以子状态就有了，dp[u][j][0/1/2]dp[u][j][0/1/2]dp[u][j][0/1/2]表示uuu的子树里面选jjj个点，而且uuu的子树里面有多...

传送门 考虑dp状态dp[u][i][0/1][0/1]dp[u][i][0/1][0/1]dp[u][i][0/1][0/1]表示dp到节点uuu，uuu的子树里面放了iii个监听设备，uuu自己有没有被放，uuu自己有没有被监听。 注意到我们要满足题目的条件，所以只有u的子树内的其他点（不包含u）都被监听，才会算入dp方案数。 接下来是恶心的分类讨论： 1.dp[u][i][0][0]1...

传送门 不记得是哪场比赛切的题了，发现点ppp的两个不同子树中任选两个点作为(ui,vi)(u_i,v_i)(ui​,vi​)，他们的LCALCALCA 都是pip_ipi​ 所以答案为∑u,v∈ch[p],u!=vsz[u]∗sz[v]\sum_{u,v \in ch[p],u!=v} sz[u]*sz[v]∑u,v∈ch[p],u!=v​sz[u]∗sz[v]，剩下容斥乱搞一下就可以了。...

传送门 ProProPro 有n个城市，编号依次为1到n，同时有m条单向道路连接着这些城市，其中第i条道路的起点为Ui，终点为Vi 。(1<=Ui < Vi <= n)。 特工团队一共有3名成员：007，008，以及009，他们将要执行q次秘密任务。 在每次任务中，三人可能会处于三个不同的城市，他们互相之间通过对讲机保持联络。编号为i的城市的无线电频为Wi，如果两个城市的...

一个裸的完全背包，考虑将2k2^k2k当做物品，做完全背包即可。 12345678910111213141516171819202122232425262728293031323334353637#include <iostream>#include <cstdio>#define MAXN 1000005#define MAXM 24#define MOD 1000...

传送门 我们发现一个很有趣的性质：假设a[i]==a[j]a[i]==a[j]a[i]==a[j]且i<ji<ji<j，先把[i+1,j−1][i+1,j-1][i+1,j−1]区间中的回文串消到只剩一个，这一个回文串会和两段的a[i],a[j]a[i],a[j]a[i],a[j]构成一个更大的回文串，所以在消去这个回文串的同时，顺便消掉两端的a[i]a[i]a[i]和a[...

传送门 这道题把坑设在了数据范围里面，第一眼看上去没有思路，第二眼发现m≤2m \le 2m≤2，思路瞬间来了。 分情况讨论，分为m=1m=1m=1情况和m=2m=2m=2的情况。 声明，为了简略，我们设sum(l,r)sum(l,r)sum(l,r)为∑i=lra[i]\sum_{i=l}^{r}a[i]∑i=lr​a[i]，sum1(l,r)sum1(l,r)sum1(l,r)为∑i=...

传送门 （题目描述有毒，这里的树不是指nnn点n−1n-1n−1条边的连通图，而是普普通通的树（植物）） 考虑DPDPDP，很容易想到一个O(nC2)O(n C^2)O(nC2)的DPDPDP，令dp[i][j]dp[i][j]dp[i][j]为第iii棵树拔到jjj的高度，且111到iii的所有树之间都连了线的最小花费，我们有： dp[i][j]=min⁡{dp[i−1][k]+c×∣j−...

传送门 比较有意思的DPDPDP 题目，考虑转化题目条件： 原题目：对于任意连续的一段，男女数目之差不超过kkk 转化成：对于所有的连续的段，男女数目之差的最大值不超过kkk 然后就可以DPDPDP了，令dp[i][j][x][y]dp[i][j][x][y]dp[i][j][x][y]为前i+ji+ji+j人中iii人为男孩，jjj人为女孩，对于前i+ji+ji+j人中所有连续的段，男减女...

传送门 假设没有不允许两个相同的数配对的条件，那么直接将ABABAB数组排序一遍，每一位每一位配对即可。 现在不允许两个相同的数配对，还是考虑贪心，如果出现如图的匹配情况，即a[i]a[i]a[i]和b[i−alb]b[i-alb]b[i−alb]匹配，其中alb>2alb>2alb>2。 发现这种情况肯定不是最优的，因为我们发现一定存在一个a[j](j≤i−1)a[j]...