起因：cjx暑假集训的时候出了道题，老师说可以点分治。但是我最初的想法其实是换根处理，但怎么想发现都行不通，因为要同时维护DFS序和权值。于是就没想了。后来10.5和xyh进行长达30s的讨论导游的工作那题，说了我这个想法，xyh觉得有道理，对要求解的问题具体化，于是我才想出了分块

空夜Description给定\(n\)个节点的树，每个点有点权\(a_i\)，对于每个\(i\)，求出\(\sum_{j}\lfloor\frac{a_i}{2^{dis(i,j)}}\rfloor\)。\(dis(i,j)\)表示\(i\)到\(j\)的树上最短路径。Solution对于每个\(i\)都要求答案，等价于求以\(i\)为根的树的答案，可以想到

树形DP中的换根DP问题又被称为二次扫描，通常需要求以每个点为根时某个式子的答案。这一类问题通常需要遍历两次树，第一次遍历先求出以某个点（如\(1\)）为根时的答案，在第二次遍历时考虑由根为\(u\)转化为根为\(v\)时答案的变化（换根）。这个变化往往分为两部分，\(v\)子树外的点到

背景4.14打abc的时候一眼e题是换根模板，但是我不会，于是就来补档了。什么是树形dp/换根dp一种在树上的dp，一般用dfs进行状态转移。树形dp一般用儿子来更新父亲的答案。换根dp一般在第二次dfs时用父亲的答案转移到儿子去。引入经典树形dp例题：没有上司的舞

\(T1\)题面，由于是正方形，我们不需要枚举左上和右下两个端点，只需枚举左上端点和正方形边长，而正方形边长如果用二分枚举，常数大，过不了。这里考虑矩形中一个技巧，即在矩形中充分利用已经求过的信息，故可以想到递推，设\(l[i][j]\)表示\((i,j)\)为左端点最大正方形长度，则\(l[i][j]\)最少为\(

问题引出:给出\(n\)个点的树，求出分别以不同的\(i\)为根时，所有结点深度的和，根节点的深度为\(0\)。首先我们有个自然的暴力思路,也就是以每个节点为根节点做一遍\(dfs\)这样的复杂度是\(O(n^2)\)级别的,所以要进行优化看下图:我们首先假设每个节点具有点权,明显这

P3478[POI2008]STA-Stationlink给定一个\(n\)个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。一个结点的深度之定义为该节点到根的简单路径上边的数量。对于全部的测试点，保证\(1\leqn\leq10^6\)，\(1\lequ,v\leqn\)，给出的是一棵树。思路：树

大致步骤 换根dp大致步骤 方法一：（up数组）(1)g[i]以i为根的子树（不是整棵树），由孩子节点推过来(2)up[i]i节点往上走的最大属性(3)f[i]整棵树（不是子树）记录一些值 方法二：加减法(1)g[i]以i为根的子树（不是整棵树），由孩子节点推过来(2)f[i]整棵树（不是子树）记录一

板子P2986[USACO10MAR]GreatCowGatheringGP3478[POI2008]STA-StationP3047[USACO12FEB]NearbyCowsG很好的一题f[i][j]表示与点i(向下(点i儿子1中的点))距离为j的点的权值和g[i][j]表示与点i(所有)距离为j的点的权值和需要特别注意的是刚开始时g[i][j]=

真的是公公又式式啊换根dp的宗旨是利用已有的信息来推出其他信息换根dp的题目通常是树，o(n)时间空间，要求每一个点的答案。我们如果指定了以1为根，那么可以算出每个点往下的答案，但是每个点的父亲对本身的贡献还没有算，所以我们可以记录dp1,dp2两个数组，分别记录专用图注意，dp1[u]

换根dp  背景对于一颗无根树而言，假如我们有着把每个节点当成根节点的需求时，那么原先的直接从根节点开始搜索就无法满足我们的时间效率此时我们就需要考虑转换策略研究，有没有什么好的方法能够不去把每个节点当成根节点都跑一次搜索考虑我们手中已有的信息，我们知道跑一次搜

题意：给出一个\(n\)个点的树（边权为\(1\)）和集合\(S\)，求有多少个点集\(T\)可以被表示为离\(S\)中的一个点\(u\)距离不超过\(d\)的点构成的集合（下文称为\(u\)的\(d\)级邻域）。考虑\(S\)为所有点的特殊情况：我们直接求每个点邻域的个数再求和，会算重一些点集，这种情况

啊啊啊啊啊啊啊啊啊啊啊啊画图累死我了额，这不菜根快乐DP（根）吗换根DP，即换根树形DP平常树形DP指定一个根，但万一邪恶出题人让你求多个点为根的情况呢？你们可能会想：多跑几遍不就好了！不可以的，直接TLE。这有个树，B是A之后的树根（拎上去）：B成为树根后：画风突然转变但是！其实有些没变！

懒得写代码了1.http://oi.nks.edu.cn/zh/Problem/Details?cid=2719&tid=F 首先有个单次询问O（n）的换根DP做法。像这种每次找一类点计算答案的题，考虑虚树。有个结论：相遇点选在颜色为x或y的点上不会更劣所以只需要在同时包含x和y色的虚树上换根DP就行了但复杂度波动不定。当ma

[学习笔记]换根DP的常用处理方式换根DP，又称作二次扫描法，通常用于“对每个根求出树形DP的答案”。以每个点作为根节点进行一次树形DP的代价通常无法承受，因此我们会使用两次DFS：第一次DFS指定一个点为根节点，运行一次常规的树形DP。第二遍DFS进行换根DP，得到将根转移

这道题目一眼ddpddp，顾名思义，应该（我没学过）就是中间代价会变化。看看洛谷模板，是需要用到树剖的那么中间代价的变化分为dp值的变化和转移时节点本身代价的变化，这里肯定就是只有dp值的变化了想一下，如果只有一个节点被限制了，那么是不是很像换根DP？所以只用换根就好了如果有两个节点

换根树形动态规划考虑以1为根的情况,size[i]表示以i为根的子树中有多少个点,f[i]表示考虑以i为根的子树,i到子树其他所有点的距离的和;假设j是i的儿子,以j为根的子树对f[i]的贡献为f[j]+size[j]\[f[i]=\sum_{j\inson(i)}(f[j]+size[j])=\sum_{j\inson(i)}(f[j])+size[i

请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。这个点被称为树的中心。题解：https://www.cnblogs.com/dx123/p/17302104.html评测：https://www.acwing.com/problem/content/1075/暴力做法是以每个点为根，求出从根向下走的最远距离，这个过程需要做n遍，每一遍dfs的复杂

换根DP又称二次扫描。特征：树中没有指定根节点。采用不同的节点作为根，答案可能不一样。模板P3478[POI2008]STA-Station暴力解法：枚举根节点，求以该节点作为根时，所有节点的深度之和，时间复杂度O(n^2)优化：直接通过父节点的深度之和，得到子节点的深之和：子节点变为根节点之后

大家好，我是毒瘤，喜欢用玄学算法过题。发现题解区没有这个做法，于是来发一篇。思路不难发现如果一个点对\((u,v)\)的距离为\(d\)，那么在这棵树以\(u\)为根时，\(v\)的深度为\(d\)。于是考虑换根DP。首先思考如何计算答案。显然我们可以将查询离线下来，然后当换根到以\(u\)

树上的最大权连通块：一种换根动态规划与贪心算法的结合在计算机科学中，树是一种非常特殊的数据结构，不仅因为它们在存储数据时的效率，还因为它们提供了一种非常直观且强大的方式来解决各种问题。今天，我们将探讨一种特殊类型的问题，即在一棵树中找到一个特殊的子集或连通块，该子集中的节

看到网上的方法多多少少比较复杂，所以决定写一下。首先对于一道换根dp题应该是先要会不换根版本的。然后可以按照欧拉序（括号序）换根。对于欧拉序中相邻的两个节点必有一条边把它们相连，所以换根的时候只需要从新统计\(1\)个子树的信息。觉得自己的语言表达能力太烂，还是上题目比

一、换根树形动态规划换根树形动态规划又称二次扫描，相较于一般的树形动态规划，有如下特点：以树上不同的节点为根，其解不同求解答案时，不能只求解某一点的信息，而是求解所有点的信息无法通过一次搜索来求解答案二、例题1.[DaimayuanOnlineJudge.距离和]题目描述有一棵\(n\)

换根dp一般不会指定根节点，并且根节点的变化会对一些值进行改变。因此我们需要转移根。换根dp一般需要预处理一下一个节点的值，然后对于任意节点开始树上dp转移。所以我们常用两次dfs，第一次dfs预处理，第二次dfs为树上dp。一般比较套路。接下来会给出一个典型例题。典例1：L

换根法思路：自下而上递推；自上而下递推。P3478[POI2008]STA-Station题目描述：思路：个节点\(u\)为根的子树大小\(s[u]\)。然后我们设\(f[i]\)为以\(i\)为根时所有节点的深度之和，\(j\)为\(i\)的子节点。那么对于所有\(j\)的子节点，深度都减\(1\)，所以总共减少了