我是考场策略大师A\(O(|s||x||y|)\)DP是朴素的，上个bitset除个\(w\)即可。B称花费\(A\)的操作为一操作，花费\(B\)的操作为二操作。注意到可以先做一操作（选出若干条边，加它们的重边）再做二操作，而做完一操作之后，设有\(k\)个度数为奇数的点（下称“奇点”），则需要做\(k/2-

树的难题题意给出一个无根树。树有\(N\)个点，边有权值。每个点都有颜色，是黑色、白色、灰色这三种颜色之一，称为一棵三色树。可爱的Alice觉得，一个三色树为均衡的，当且仅当，树中不含有黑色结点或者含有至多一个白色节点。然而，给出的三色树可能并不满足这个性质。所以，Alice打

01-Trie的应用01-trie就是把一个整数的二进制表示看成一个01字符串然后插进字典树里。因为我们的01-trie要体现像平衡树一样的大小关系，同时有时还需要知道异或最值等信息，所以一般都是从高位往低位插。01-trie的一个节点一般可能需要维护这些信息：左右儿子、子树内包含的

陈年笔记，现在可能不会了。点分治Q1：基本思想是什么？将路径分为经过\(u\)和不经过\(u\)的两类，在每次分治中计算经过\(u\)的路径数量。Q2：如何统计？一般：遍历\(u\)的每个子节点\(v\)，把\(v\)子树内的节点记录下来，得到答案并更新数组。容斥：把\(u\)子树内的节点都记录下

A\(n\)个人之间有若干认识关系，你要把这些人划分为两个集合，使得集合里的每个人都认识偶数个人。求方案数，\(n\le1000\)。设每个人的状态为\(0/1\)表示两个集合，那么第\(i\)个人在其集合里认识的人个数是\(\sum_{j}(x_i\otimesx_j\otimes1)\)。解这个方程，高斯消元，若自由

https://www.becoder.com.cn/contest/5423「HNOI2012」集合选数感觉差不多会。7/25sh杂题听课情况NOI2018冒泡排序【40】几乎不会麦田里的守望者【40】打表找规律、最后dp不太理解星空列车【40】完全不会WereYouLast：知道怎么做，但是不知道为什么是对的A

题目传送门前置知识二分答案|树形DP解法答案显然具有单调性，考虑二分答案。设当前二分出的答案为\(mid\)，则等价于覆盖距离为\(mid\)的情况下进行选点。做法同luoguP3942将军令，考虑进行贪心，对于深度最深的叶节点将选择的点放在边界时，即取\(mid\)级祖先时，覆盖的范

\(\text{Link}\)题意给你一颗\(n\)个结点的树，有\(k\)次操作，第\(i\)次操作：每个点初始都处于未激活状态；以\(p_{i,j}\)的概率激活点\(j\)；对于每个未激活的点\(i\)，如果存在激活的结点\(j,k\)且\(i\)在\(j\)到\(k\)的路径上，则\(i\)也会被激活。给出\(v_{i

一T1：小奇挖矿2因为只能走4步或7步，可以发现，当步数差\(\ge18\)时，一定能到达。而当步数差\(<18\)时，枚举出所有能到达的情况即可。#include<bits/stdc++.h>#definergregister#defineqwq0#defineintlonglongusingnamespacestd;constintN=1e5+3;intn,m;struc

P3354[IOI2005]Riv河流如果我们设\(f_{u,j}\)表示子树\(u\)内放了\(j\)个伐木场的答案，发现很难转移。我们多加状态，设\(f_{u,i,j}\)表示子树\(u\)放了\(j\)个伐木场，木材全部运到\(i\)去最小代价。\(i\)是\(j\)祖先。继续设\(g_{u,i,j}\)表示\(u\)建了伐

郊游首先需要快速找到当前适配度最大的一对小朋友。容易发现\(a,b\)的适配度即为\(a,b\)二进制下最长公共后缀的长度，于是先翻转所有数的二进制串并插入到Trie中。那么\(a,b\)的适配度即为\(a,b\)所代表叶子节点的\(\rmLCA\)（最近公共祖先）深度。若Trie中以\(x\)

NOIP2023-div2模拟赛25A原题发现实际上是一个直角边与坐标系垂直的直角三角形，直角顶左上且其上字符为J，右边的字符是O，底下的字符是I。于是可以在J处统计贡献，另外两个做后缀和处理即可。B卡常做法里不要写#defineintlonglong!!!\(O(n\logn)\)：所有数按数值从大到小

思路对于每个\(1\lei\len\)的\(i\)都要求答案，那我们考虑dp，去思考如何转移\(f_i\)。先不考虑全局，只考虑子树内的贡献，设\(g_u\)表示以\(u\)为根的子树内，对\(u\)来说满足条件的点对数。对于\(u\)的儿子\(v\)，对\(v\)来说合法那么对\(u\)来说也一定合法。因为

P5642人造感情首先考虑如何求\(W(U)\)。对于路径\((x,y,w)\)，我们将它挂在\(u=lca(x,y)\)上，记\(f_u\)表示仅考虑\(u\)子树内的链获得的最大值，\(s_u=\sum_{v\inson_u}f_v\)，表示仅考虑\(u\)子树内的链，且钦定\(u\)不被占用的最大值。\(s_u\)易求，若\(u\)不被占用，\(

哦哦牛皮给定一棵树，你需要加入一些边，使得它成为一个简单无向图，要求：图的直径等于原树直径加入任何一条新边都会让图的直径变小。求方案数对\(998244353\)取模。\(1\len\le2\times10^5\)考虑找到新图的一对距离最远的点，将其它点按照到它们的距离标号并分层。由于第

具体思路题目问的是三元组\((x,z,y)\)使得\(x\)可以到达\(z\)，且\(z\)可以到达\(y\)，求三元组\((x,z,y)\)的数量。我们转化一下问题，就是问\(x,y\)之间所有不重复路径的点的并集减\(2\)。显然，无向图中任意一个点都属于一个点双连通分量。那么问题转化为\(x,y\)之

虽然做法大致相同，但是本篇题解将会讲述如何想出正解，分享我的思路。望通过。首先看到题目，容易想到一个简单很多的情况：在一条链上，且终点确定。此时就可以把终点两边的点分开，分别计算到终点的距离之和，看是否相等即可。没有确定终点时，枚举一个终点即可。考虑将这种做法带入本题。先

将关键点以深度为第一关键字，编号为第二关键字从小到大排序。建完虚树后依次考虑这些关键点可能的管辖的结点。每次在虚树上向上跳，当遇到某个已经被访问过的结点时，根据我们的排序条件，显然再往上的结点就一定不是当前关键点管辖的了。但是在向上跳的这条链上的子树内的结点不一定由

看错题看成只能交换相邻节点颜色了/fn每次操作交换两个节点颜色，可以转化为统计最终合法颜色序列相比开始，最少有多少个红点变成黑点。可以考虑一个类似树形dp的过程，对于每个节点我们钦定下它会被哪个节点“笼罩”，同时由于黑点数量有限，我们还需要记录下子树内已经用了多少个黑点

经典最大独立集问题可设\(dp_{u,0/1}\)表示\(u\)为根的子树内，不选/选\(u\)的独立集最大权。本题求方案数，且\(k\)这么小，暗示我们将上面状态压到维度，设\(f_{u,i,j}\)表示以\(u\)为根的子树内，\(dp_{u,0}=i,dp_{u,1}=j\)时的方案数，此时状态数\(O(n^3k^2)\)，转移总复杂度

突然发现深究一些树上问题还是挺有意思的哈。显然对于同一种权值的任意两个结点，其两端的部分都是不合法的。维护两个标记表示子树内均不合法与子树外均不合法即可。但相同权值的点对数量是\(O(n^2)\)的，我们要优化这个过程。发现很多点对都是无用的。DFS下去，遇到一个\(x\)

  题目描述一颗树nn个点，n−1n−1条边，经过每条边都要花费一定的时间，任意两个点都是联通的。有KK个人（分布在KK个不同的点）要集中到一个点举行聚会。聚会结束后需要一辆车从举行聚会的这点出发，把这KK个人分别送回去。请你回答，对于i=1∼ni=1∼n，如果在第ii个点举

[CSP-S2019]树的重心因为这道题令我十分兴奋，所以来写一下做完后的思考。这道题用到了树的重心的种种性质，在写解法的时候会一一点出其用处。首先，枚举每一条边，然后各自\(O(n)\)扫一次的\(O(n^2)\)做法是简单的。那么接下来，就会出现不同的解法了：优化\(O(n)\)求解的过程

B考虑我们实际上仅仅在钦定\((u,v)\)不切断时需要通过\(v\)所在子树的异或和这个状态来更新\(u\)对应异或和的状态，此时状态内每一位都是独立的。所以直接拆位仍然能够转移，得到\(f_{i,j,0/1}\)表示节点\(i\)子树内第\(j\)位异或和确定情况下的答案。而在钦定\((u,

尝试理解，感谢cz_xuyixuan的题解。算作是很多情况的补充说明。我们不妨先二分答案，将\(\gemid\)的设为\(1\)，\(<mid\)的设为\(0\)，于是问题转化为了权值均为\(0/1\)的版本。我们称一棵树的大小为其非叶节点数。我们称一棵大小为奇数的树为奇树，大小为偶数的树为偶树。对