不错的树形 dp 练习题——树链剖分（非模板）
Sweetlemon
2019-12-18 19:55:42
$\Large{\text{可以得到比 std 更优的答案！值得一看！}}$
既然能得到比 std 更优的答案（连样例都有更优的解），要不要加强数据？（雾）
空说无凭，给出一组更优的样例输出（其实人力求解也可以得到这个更优解）。
```plain
2
6
7
9
0
11
0
0
13
0
0
0
14
0
```
其实只是把 $4$ 的重儿子从 $8$ 改成了 $9$ 而已，原答案是 $18$，新答案是 $17$。
（可能是为了降低难度才把 std 的解改劣？如果是这样，那就不要加强了吧~）
（吹水完毕，题解正文开始）
### 树链剖分（非模板）
这道题应该还是有不少部分分的方法的，比如随便选一个儿子输出（雾），或不管三七二十一直接重链剖分，都可以拿到一定的分数。
下面介绍一种思路比较自然、实现不困难、可以得到比 std 更优的答案的树形 dp 方法。个人认为应该已经达到了理论最优解，欢迎 hack。
#### 条件转化
题目中的“所有查询经过的轻重链的总数”不是特别容易统计，因此我们考虑把它进行转化。
初始的一步是把 $x\rightarrow y$ 的路径拆成 $x\rightarrow \mathrm{LCA}(x,y),\ y\rightarrow \mathrm{LCA}(x,y)$ 两条树链，这一步应该很容易想到。这一次查询经过的链的总数就等于这两条树链包含的链的数量之和。（注：此处“树链”指的是树上一点到它的某个祖先的路径。）
那么如何描述一条树链经过的链的数量呢？
假设我们是暴力统计这个量，那么我们的思路可以是这样的：从 $x$ 一直跳到 $\mathrm{LCA}(x,y)$，考虑每一条边，如果这一条边和上一条边都是重边，那么这两条边在同一条重链上，不需要重复统计，答案不变；否则答案加 $1$。
总结上面的过程，“一条树链经过的链的数量”可以描述为“树链的长度减去树链中相邻重边对的数量”，也就是假设这条树链的边依次是 $e_1,e_2,\cdots,e_k$，那么答案就应该是 $k-\sum_{i=1}^{k-1}[e_i,e_{i+1}\text{都是重边}]$。（注：$[\text{条件}]$ 表示条件成立时这个数是 $1$，否则是 $0$。）
由于树链中边的数量是定值，所以想要让“所有查询经过的轻重链的总数”最小，就应该让“所有查询的树链所经过的相邻重边对”最多。
这样我们就有了比较方便的统计量。方便在哪里呢？原来的“经过轻重链”所涉及的状态比较复杂，相比之下“相邻重边对”就简单多了——这个状态只与“这一条边”和“上一条边”有关。
#### 状态和状态转移的设计
这道题是要决策“选哪个重儿子”，又有了比较容易表示的统计量，我们觉得可以试试树形 dp。
按照树形 dp 的套路，我们只考虑某一棵子树。
为方便叙述，先定义两个概念。相邻重边对需要有一个“统计位置”。这里我们把树链上相邻两条边上深度最大的点称为这个相邻边对的“基点”，并把基点作为相邻重边对的统计位置。换句话说，相邻边对就是基点往上跳两层。可以设 $w[y]$ 表示所有查询路径中，以 $y$ 为基点的相邻边对的出现次数。选择基点进行统计的理由是，每个基点唯一对应一条相邻边对。另外，我们称基点的父亲为“中点”，中点是相邻边对的两条边的公共点。
我们设 $f'[x]$，表示在所有划分 $x$ 子树的轻重儿子的方案中，中点在 $x$ 子树中（中点在 $x$ 子树中，也就意味着基点一定是 $x$ 的子孙）的有效相邻重边对的最大数量。这里的有效指的是出现在查询路径中，而且“数量”指的是出现在查询路径中的总次数。$f'[1]$ 达到最优时，我们也就得到了这道题的最优解。
那么我们考虑这个状态如何转移呢？
假设我们已经算出了 $x$ 的所有子节点的 $f'$，那么 $f'[x]$ 比儿子多出的那一部分，就是以 $x$ 为中点（也就是以 $x$ 的儿子为基点）的相邻重边对，而这就涉及到“$x$ 是不是重儿子”的问题；但在我们的状态中，没有办法处理“$x$ 是不是重儿子”！
怎么办呢？加上去不就好了？设 $f[x][0/1]$ 表示在 $x$ 不是（$0$）/ 是（$1$） 重儿子的情况下，在所有划分 $x$ 子树的轻重儿子的方案中，中点在 $x$ 子树中的有效相邻重边对的最大数量。当 $f[1][0]$ 取到最优解的时候，就得到本题的答案。
现在似乎就比较容易转移了。
如果 $x$ 不是重儿子，那么不能产生以 $x$ 为中点的相邻重边对，此时只需要在 $x$ 的儿子中选出重儿子。$f[x][0]=\max\limits_{y\in \mathrm{children}[x]}(f[y][1]+\sum\limits_{u\in \mathrm{children}[x],u\neq y}f[u][0])$。式中的 $y$ 是枚举的重儿子。
如果 $x$ 是重儿子，那么会产生以 $x$ 为中点的相邻重边对。假如 $y$ 是 $x$ 的重儿子，那么相邻边对 $y\rightarrow x\rightarrow \mathrm{par}(x)$ 就成为了相邻重边对。回忆一下，我们设 $w[y]$ 表示所有查询路径中，以 $y$ 为基点的相邻边对的出现次数；那么新产生的相邻重边对的个数就是 $w[y]$。$f[x][1]=\max\limits_{y\in \mathrm{children}[x]}(f[y][1]+w[y]+\sum\limits_{u\in \mathrm{children}[x],u\neq y}f[u][0])$。
这个树形 dp 的主框架已经完成了。我们只需要在计算 $f$ 的过程中，记录好“决策点”，也就是使 $f[x][0],f[x][1]$ 取最大值的 $y$ 分别是多少，最后输出答案时根据 $x$ 最后是不是重儿子输出相应的决策点即可。
现在的问题是，如何计算 $w[y]$ 呢？
#### 预处理工作
查询一条路径 $x\rightarrow y$ 的时候，假设这条路径是 $x\rightarrow u\rightarrow \mathrm{LCA}(x,y) \rightarrow v \rightarrow y$，其中 $u,v$ 都是 $\mathrm{LCA}$ 的直接儿子，那么从 $x$ 到 $u$、从 $y$ 到 $v$ 的点（不含 $u,v$）的 $w$ 都要加 $1$（回忆一下，基点“往上跳两次”的次数是 $w$）。
怎么实现这个加 $1$ 呢？我们可以用 ~~树链剖分+线段树~~ ~~树链剖分+树状数组~~ 树上差分（因为是全部加完再查询，相当于离线操作，因此差分就够了）。设 $\mathrm{delt}[x]$ 表示 $x$ 对 $x$ 和 $x$ 的祖先的 $w$ 的贡献；也就是 $\mathrm{delt}[x]$ 加 $1$，就相当于给 $x$ 和 $x$ 的祖先的 $w$ 都加了 $1$。那么处理每个查询时，只需 `delt[x]++,delt[y]++,delt[u]--,delt[v]--`；最后令 $w[x]$ 为以 $x$ 为根的子树的 $\mathrm{delt}$ 之和即可（因为只有子孙才对 $x$ 有贡献，而子孙的 $\mathrm{delt}$ 之和便是它们对 $x$ 的总贡献）。
还有一个小问题，如何求出 $u,v$ 呢？我们选择用倍增 LCA，在倍增的过程中很容易得到 $u,v$。
另外，如果 $x$ 或 $y$ 本身就是 $\mathrm{LCA}$ 呢？或者 $x,y$ 本身就是 $\mathrm{LCA}$ 的直接儿子呢？这些问题都不大，我们只要令 `u=x` 或 `v=y`，一加一减就抵消了。写代码的时候注意处理。
#### 思路总结
综上，这题的主要解决步骤是：
1. 读入树，做好 LCA 的预处理，$O(n \log n)$
2. 读入查询，用倍增 LCA 找 $u,v$，做树上差分，$O(q \log n)$
3. dfs 一遍，由差分得到 $w$，$O(n)$
4. 进行树上 dp，求出 $f$ 的决策点，$O(n)$
5. 根据决策情况确定重儿子，输出答案，$O(n)$
总复杂度是 $O(n\log n)$ 级别的，瓶颈是 LCA。
这道题的主要启示就是，拿到题要勤于转化题目的条件，把不好处理的条件转化为熟悉的、容易处理的条件，这样就比较容易解题了。
#### 代码
代码比较长，但是基本都是套路，因此也不难写。
吐槽一下数据太弱，把我一份连样例都没过的错误代码（那份代码的 LCA 写炸了）放过去了。建议把样例加入数据中（笑）。
评测记录在[这里](https://www.luogu.com.cn/record/28552121)。可以看到答案基本上都比 std 优。
```cpp
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAXIOLG 25
#define FILENAME(x)\
freopen(x".in","r",stdin);\
freopen(x".out","w",stdout);
#define LOWBIT(x) ((x)&(-(x)))
#define MAXN 100005
#define MAXM 200005
#define MAXLG 17
using namespace std;
typedef long double ld;
typedef long long ll;
typedef ll io_t;
//快读快写
io_t shin[MAXIOLG];
io_t seto(void);
void ayano(io_t x,char spliter='\n');
int n;
//存图
int g[MAXM];
int fst[MAXN],nxt[MAXM],edges=0;
//倍增父亲数组, 儿子数量, 深度
int par[MAXLG][MAXN],chs[MAXN],depth[MAXN];
//log 2 的值的预处理
int lg[MAXN];
//差分数组，后来直接用来表示 w
int delt[MAXN];
//f 数组和决策点数组
int f[MAXN][2],h[MAXN][2];
//isp=is preferred，是不是重儿子；pr[x] 表示 x 的重儿子
int isp[MAXN],pr[MAXN];
void dfs1(int x,int pa); //预处理 LCA
int jmp(int x,int k); //x 往上跳 k 层
void solve(int x,int y); //处理查询
void dfs2(int x,int pa); //树上差分的求和, delt 变成 w
void dfs3(int x,int pa); //树上 dp
void dfs4(int x,int pa); //由决策点得出答案
void addedge(int u,int v); //加边
int main(void){
n=seto();
int q=seto();
{
//预处理 log 2
lg[0]=lg[1]=0;
int tlg=0;
for (int i=2;i<=n;i++)
(i==LOWBIT(i))?(tlg++):(0),lg[i]=tlg;
}
for (int i=1;i<n;i++){
int u,v;
u=seto(),v=seto();
addedge(u,v),addedge(v,u);
}
//预处理 LCA
dfs1(1,0);
for (int tlg=1,lgn=lg[n];tlg<=lgn;tlg++){
int ulg=tlg-1;
for (int i=1;i<=n;i++)
par[tlg][i]=par[ulg][par[ulg][i]];
}
//处理查询
while (q--){
int u,v;
u=seto(),v=seto();
solve(u,v);
}
//树上差分的求和, delt 变成 w
dfs2(1,0);
//树上 dp
dfs3(1,0);
//由决策点得出答案
isp[1]=0; //1 不是重儿子
dfs4(1,0);
//输出答案
for (int i=1;i<=n;i++)
ayano(pr[i]);
return 0;
}
void dfs1(int x,int pa){
//预处理 LCA
par[0][x]=pa,depth[x]=depth[pa]+1;
for (int ei=fst[x];ei;ei=nxt[ei]){
int v=g[ei];
if (v==pa)
continue;
dfs1(v,x),chs[x]++;
}
}
void dfs2(int x,int pa){
//树上差分的求和, delt 变成 w
for (int ei=fst[x];ei;ei=nxt[ei]){
int v=g[ei];
if (v==pa)
continue;
dfs2(v,x);
delt[x]+=delt[v];
}
}
void dfs3(int x,int pa){
//树上 dp
if (!chs[x]){
//叶子节点的 f 和决策点都是 0
f[x][0]=f[x][1]=h[x][0]=h[x][1]=0;
return;
}
int s0=0; //所有儿子 u 的 f[u][0] 之和
for (int ei=fst[x];ei;ei=nxt[ei]){
int v=g[ei];
if (v==pa)
continue;
dfs3(v,x);
s0+=f[v][0];
}
int f0=-1,f1=-1; //当前最优 f[x][0], f[x][1]
int h0=0,h1=0; //当前决策点
for (int ei=fst[x];ei;ei=nxt[ei]){
int v=g[ei];
if (v==pa)
continue;
int tf0=s0-f[v][0]+f[v][1];
int tf1=tf0+delt[v];
(tf0>f0)?(f0=tf0,h0=v):(0);
(tf1>f1)?(f1=tf1,h1=v):(0);
}
f[x][0]=f0,f[x][1]=f1;
h[x][0]=h0,h[x][1]=h1;
}
void dfs4(int x,int pa){
//由决策点得出答案
pr[x]=h[x][isp[x]]; //根据 x 是不是重儿子，选择相应决策点
(pr[x])?(isp[pr[x]]=1):(0);
for (int ei=fst[x];ei;ei=nxt[ei]){
int v=g[ei];
if (v==pa)
continue;
dfs4(v,x);
}
}
inline int jmp(int x,int k){
//x 往上跳 k 层
if (!k)
return x;
for (int i=0,lgk=lg[k];i<=lgk;i++){
int tpw=1<<i;
(k&tpw)?(x=par[i][x]):(0);
}
return x;
}
void solve(int x,int y){
//处理 x y 查询
if (x==y || par[0][x]==y || par[0][y]==x)
//特殊情况判断
return;
delt[x]++,delt[y]++;
int xd=depth[x],yd=depth[y],dd;
if (xd<yd)
swap(x,y),dd=yd-xd;
else
dd=xd-yd;
int txans=x,tyans=y; //txans, tyans 表示 u, v
int xjmp=jmp(x,dd);
if (xjmp==y){
//LCA 就是 y
txans=jmp(x,dd-1);
tyans=y;
}
else {
x=xjmp;
for (int tlg=lg[depth[x]];~tlg;tlg--)
(par[tlg][x]!=par[tlg][y])?(x=par[tlg][x],y=par[tlg][y]):(0);
txans=x,tyans=y;
}
delt[txans]--,delt[tyans]--;
}
void addedge(int u,int v){
//加边
edges++;
g[edges]=v;
nxt[edges]=fst[u],fst[u]=edges;
}
io_t seto(void){
//快读
io_t ans=0;
int symbol=0;
char ch=getchar();
while (!isdigit(ch))
(ch=='-')?(symbol=1):(0),ch=getchar();
while (isdigit(ch))
(ans=ans*10+(ch-'0')),ch=getchar();
return (symbol)?(-ans):(ans);
}
void ayano(io_t x,char spliter){
//快写
if (!x){
putchar('0'),putchar(spliter);
return;
}
if (x<0)
putchar('-'),x=-x;
int len=0;
while (x){
io_t d=x/10;
shin[len++]=x-d*10;
x=d;
}
while (len){
len--;
putchar(shin[len]+'0');
}
putchar(spliter);
}
```