小衣同学的博客

2. 对于T2树上每个非叶节点x，对于x的每个儿子y，都至少存在一个z，满足在T1树上，z和x有连边。找到T2的一个根满足T2是T1的starch tree，有多个输出任意一个即可，无解输出-1。所以将其转化为预处理T1上每个(x,z)边的贡献，一旦无根树T1上(x,z)是相连的，那么有根树T2有向边y->x（y是有根树T2上z->x路径上x相邻的点）就是合法的，T2有根树上，对于每个x的直连儿子y，都至少存在一个z，z在T2的y的子树里，其中T1是无根树，T2是有根树，但还未确定根，

一棵树，考虑加边的过程，加一条边减少一个连通块。那么，逆向这个过程，没删一条边，就多一个连通块。连通块贡献=点的贡献-边的贡献，然后分开统计。森林：点的个数=边的个数+连通块个数。树：点的个数=边的个数+1。

导出子图，即在n个点里选一个子集，选出一些点来，保留这些点之间原来的边，得到的图。f[0/1/2]表示i的子树里选了0/1/>=2棵的方案数，背包考虑子树即可，特别地，当i是非关键点的时候，i不能当叶子，这一种情况需要减掉。2. dp[i][1]表示i取，i取的话，子树可取可不取。1. 如果i是关键点，dp[i][1]是i为根的贡献。dp[i][2]表示以i为根，i不取/i取的方案数。因为，对于非叶子结点，除了lca是必经的点以外，对于一棵树，所有叶子结点，都是关键点，枚举每种颜色，对每种颜色求虚树，

初始时，选择两个位置x,y(x≠y)，代表需要对这两个位置进行操作，要把其中一个值变成另一个。也就是说，对于每个i来说，比i小的数中，只有一个数j，能和i之和凑成2的幂次，反证法显然。输出你选择的位置(x,y)，使得a[x]变到a[y]的最小步数最大，并且输出最大的步数。求树的直径即可， 即从任意点出发（不妨0），搜到带标记的最远一侧点x，问题等价于在这棵树上，标记n个点，求n个点两两距离的最大值和点号，当前值是v，你可以选择一个值k(k>=0，满足。，并且j

若in[a]<in[b]<out[a]，说明b在a的子树里，一定有in[a]<in[b]<=out[b]<=out[a]a的dfs序对应[in[a],out[a]]，b的区间对应[in[b],out[b]]2. x所在的连通块能到的最远点，一定是x这个连通块的直径的两个端点中的一个。新的树的直径的两个端点，一定是在原来两棵树直径的四个点里选两个点。利用上文提到的树的直径的性质，统一merge合法区间的直径，剩下的区间都是x的可达区间，每个区间对应一个连续的dfs序。

那么，考虑答案能不能是n，考虑将根填成n，剩下的值域[1,n-1]和[n+1,2n-1]是对称的两半。要求路径上的权值异或和（路径上的每条边的边权和每个点的点权都要参与异或）的最大值最小，但是至少有一个点会有n这一位，意味着会从偶数次变成奇数次，所以显然不成立。如果答案小于n，意味着任意一端为根的路径，n这一位都出现了偶数次，对于n个点和n-1条边，每个点需要赋权，每条边需要赋权，首先，答案不会小于n，因为n是2的幂次，占了一个二进制位。也就是异或值为n时，边用n+c，点用c。以下n-1条边，读入树边。

所以，对于所有度为2的点，尝试去用相同的方式染（比如连接父亲的染成颜色1，另一端染成颜色2），类似二分图判定的过程。按照交互机的读入方式，无法区分这两个点，也就无法决定，收到这个读入后该走颜色1还是颜色2。首先，原则肯定是，我们只要能对于深度不同的点能有所区分即可，深度相同的点染一样的无所谓。不妨第一层染1、2，第二层2、3，第三层3、1，以此类推，就可以循环下去了。如果点2的染色方案是1、2，点3的染色方案是2、1的话，颜色为1，为2，...，为k的边的条数各有多少个。

既可以理解为k个黑点到根的距离和，dis=x表示每个点上方有x个点，或者有x条边。当枚举n个根时，每个根都对应一个局部最优解，n个局部最优解的最大值，是最终解。一侧为n-1个黑点，另一侧为1个黑点，导致其贡献为n-2，总贡献和减少了2。一侧k-1个点是联通的，另一侧1个黑点，且两个连通块之间隔着一个白点，1. 有n-k条边，满足k个黑点在这些边的一侧，其代价为(n-k)*k。则可以使得只有一条边，满足一侧为n-1个黑点，另一侧为1个黑点。固定根为i，求得的dis数组，选得前k个求和，代表选了k个黑点。

②对于s->t链上的点u(u可以等于s，u不可以等于t)，将u和s->t链之间的边断开后，u的子树内的点。若走到t，则停止，问每个点经过的期望次数，答案对998244353取模。①s->t这条链，将这条链上的边定向，经过的次数，正向边=反向边+1。①部分，为点3、点4、点5，即3->4->5这条链。③将t与s->t链之间的边断开后，t的子树内的点。举个例子，以n=6，s=3，t=5这棵树为例。2. 当i=t时，一条边i->x走的次数。，其中u->v为正向边，v->u为反向边。，其中d[i]为点i的度。

Codeforces Round #838 (Div. 2) E. Tree Sum(组合数学 prufer序列)

题目n(n<=2e5)个点的树，点i有点权ai(1<=ai<=1e9)"不同根"定义为，从该点出发，到任意点的路径上都不会经历两个相同的值求图中"不同根"的个数思路来源凡神代码题解考虑到对于树上任意两个相同的值来说，这两个点之外的点，都是不合法的点，所以检查每两两个点即可，但是复杂度不符合要求画画图发现，对于每个点来说，检查离它最近的相同的值的点即可任选树根，对树进行dfs，记录dfs序，对于点u来说，如果子树v里面存在和u相同的值，则需

题目6s时限，T(T<=5)组样例，每次给出n(n<=5e5)个点的树，初始时，每个点的点权w都是0，m(m<=2e3)次操作，操作分7种，1 u v k，u到v的路径所有点点权都加k(k<=1e5)2 u v k，u到v的路径所有点点权都异或k(k<=1e8)3 u v k，u到v的路径所有点点权都减k，如果点权小于k，忽略该操作4 u v，询问u到v的路径点权和5 u v，询问u到v的路径点权异或和6 u v，询问u到v的路径点权中的最大值减

题目简化题意，1为根的有根树点i对应一个权值wi，wi在[0,n]之间对于每个i，问在其子树中有多少种深度d，满足该深度下存在两个点a、b，使得（x是给出的值，也在[0,n]之间）对于这个i，计其答案为ans[i]，要求输出对998244353取模的值思路来源官方题解题解O(nlogn)的做法由于写的比较搓，怎么写怎么T，最后无奈写O(n)bfs的过程中，一边bfs一边尺取，tong[x]维护值为x时当前出现的最大的bfs序下标，能更新当且仅当v所需要的t

题目n(n<=1e5)个节点的树，边有边权w(w<=1e9)。每个点可能是关键点，m(m<=1e5)次操作，每次将已经是关键点的改为否，反之改为是。动态维护，从任意一点出发，遍历所有关键点后回到该点，所经历的最小权值和。思路来源https://www.luogu.com.cn/blog/PinkRabbit/solution-p3320题解发现应该从关键点出发更优，考虑所有关键点的这棵虚树，应该按dfs序遍历这棵树所得代价最小，且为虚树上所有边长的二倍.

题目牛妹种了一棵苹果树。这棵苹果树有n(n<=3e5)个节点，n-1条边，每一条边都有一个权值wi(1<=wi<=1e9)​。我们定义：这棵树上的两点之间距离dist(u,v)为它们简单路径上所有边的权值和。现在，牛妹想给你q(q<=3e5)次询问，每次询问一个区间[l,r]，求。思路来源syh0313代码题解首先，考虑如果有两个连通块，如何合并，(a1,b1)是第一个连通块直径，(a2,b2)是第二个连通块直径，则合并之后的连通块直径不会劣于

题目思路来源题解代码

题目n(n<=1e3)个点的树，给定一个B(1<=B<=n)值，要求把树分成若干个块，每一块代表一个省，大小在[B,3B]之间，每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。一个城市可以作为多个省的省会。要求输出块数，每个点属于的块号，每个块的省会。思路来源https://www.luogu.com.cn/problem/solution/P232

题目给定m(1<=m<=20)，代表m叉树，和两个长度为1-26的字母串，分别代表树的前序和后序序列，求这两个序列能确定多少种不同的树思路来源https://www.cnblogs.com/BobHuang/p/8227875.html题解本质区别是，对于一个根固定的区间，第一棵子树对应一段前序和后序区间，第二棵对应一段……，假设有x棵子树，则对应了C(m,x)种选法，找到固定根时，根的每棵子树的前序后序区间，不断递归下去这个题有一个弱化版51n.

题目给出标号为1到N的点，以及某些点最终的度数，允许在任意两点间连线，可产生多少棵度数满足要求的树输入：第一行为N(0<N<=1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1输出：一个整数,表示不同的满足要求的树的个数,无解输出0思路来源https://m-sea-blog.com/archives/1661/题解prufer序列，常用来解决，和度数有关的树计数问题大数，懒得粘板子，py一发入魂代码n = in

题目给你一棵n(n<=3e5)个点有根树，q(q<=3e5)个询问，每次询问以qi为根的子树的重心是哪个点思路来源https://www.cnblogs.com/cutemush/p/11830897.htmlhttps://blog.csdn.net/chenyume/article/details/102922149题解树的重心的性质：①树的重心要么是本身，要么存在于直连儿子中节点个数最大的一个中②树的重心的所有子树中（删去该节点）最大的一颗的节点个数一定