题解 P5642 人造情感（emotion）
凉城無愛
2021-10-29 17:48:48
### 题面
给你一颗$ n $个节点的树，以及$ m$条路径$ (u, v, w)$，其中$w$可以认为是$(u, v)$这条路径的权值。一个路径集合$S$的权值$ W(S)$记为：找出$ S$的一个权值之和最大的子集，该子集满足任何两条路径没有公共点，这个子集的所有路径权值之和就是$ W(S)$。
记$ F(u, v) = w$为最小的非负整数$ w$，使得对于给定的$ m$条边组成的路径集合$ U$，$W(U \cup \{(u, v, w + 1)\}) > W(U)$。
请你计算下式，对$998244353$取模。
$$
\sum_{u=1}^n \sum_{v=1}^n F(u, v)
$$
### 题解
首先要求出$W(U)$，我们设
* $f_i$表示$i$号节点**可用可不用**，只包含$i$子树内的点的情况下最大权值。
* $g_i$表示$i$号节点**一定不用**，只包含$i$子树内的点的情况下最大权值。
* $c_i=g_i-f_i$，表示在只包含$i$子树内的点的情况下，将$i$号点空出来之后带来的贡献。
将每条路径存到$lca(u,v)$之后，有转移：
$$
g_x=\sum_{y\in son[x]}f_y\\
f_x=g_x+max\{w_j+\sum_{k\in path(u_j,v_j)}c_k\}\cup\{0\}
$$
可以用树状数组维护$\sum_{k\in path(u_j,v_j)}c_k$，而不是树剖。具体方法是将一条路径$(x,y)$差分为$(x,rt)+(y,rt)-(lca_{x,y},rt)-(fa_{lca_{x,y}})$，然后将单点加入改为子树修改，查询到根的路径改为单点查询。当然，注意到此时$(lca_{x,y},rt),(fa_{lca_{x,y}})$是没有值的，可以优化掉。
最后$f_1$就是$W(U)$。
之后考虑对每一对$(i,j)$求$F(i,j)$。再设
* $h_i$表示在没有路径从$i$的父亲插入到$i$的情况下，考虑**整棵树**的点的最小值。
此时$F(i,j)=f_1-h_{lca_{i,j}}+\sum_{k\in path(i,j)}c_k$，要理解可以将式子换一下：$f_1=h_{lca_{i,j}}+F(i,j)-\sum_{k\in path(u_j,v_j)}c_k$，即如果我们要让这条边强制被选，那么就要保证$(i,j)$这条路径空出来，看似只需要管$\sum_{k\in path(u_j,v_j)}c_k$，但实际上我们在求$f_1$的时候是可能包含那种从父亲到插下来的路径，而$\sum_{k\in path(u_j,v_j)}c_k$是不包含这种情况的($f_i,g_i$都是只包含以$i$为根的子树)，所以就需要求出$h_{lca_{x,y}}$
然后考虑求$h_i$，有两种转移方法：
* $h_y=\max\{h_x+c_x\}(y\in son[x])$
* 对于一条以$x$作为lca的路径$(u_j,v_j,w_j)$，对于节点$y$满足$fa_y\in path(u_j,v_j)$且$y\notin path(u_j,v_j)$的，$h_y=\max\{h_x-\sum_{k\in path(u_j,v_j)}c_k+w_j\}$
解释：
* 对于第一种转移，考虑如果$c_x$小于$0$，那就表示一定有以$x$为lca的路径产生了贡献，而一旦产生了贡献，那么对于x的儿子中在该路径里的(可能两个，一个或者没有)，由于不能选这一条边，其对应贡献就要$+c_x$。但由于我们不知道哪些儿子会被$+c_x$，我们就干脆给所有儿子修改，哪些被错误修改的点相比于第二种转移一定不优，所以没有影响。
* 第二种转移，对于一条路径，当我们强制这条路径被选时，那些父亲在路径中而自己不在的点，其实是可以保证没有路径从他的父亲插入他的(如果有就不满足路径不交了)。此时我们就可以更新$h_y$
考虑优化第二种转移，发现这个问题和[NOI2021] 轻重边]的处理方法很像（当然不是那些有特异性的方法）这里取其中一种给一条重链中轻儿子连续标号的方法。
具体来说就是在给一条重链标号之后，从上倒下，再给每一个重链上的点的所有轻儿子标个号。体现在代码上是这样：
```cpp
void chuli(int x){
int xx=x;
if(x^1)x=son[x];
while(x){
dfs2[x]=++dfss2,x=son[x];
}
x=xx;
while(x){
st[x]=dfss2+1;
for(int i=h[x];i;i=a[i].ne){
int y=a[i].y;
if(y==fa[x]||y==son[x])continue;
dfs2[y]=++dfss2;
}
en[x]=dfss2;
x=son[x];
}
}
void sous2(int x,int to){
dfs1[x]=++dfss1;
top[x]=to;
if(x==to)chuli(x);
if(son[x])sous2(son[x],to);
for(int i=h[x];i;i=a[i].ne){
int y=a[i].y;
if(y==fa[x]||y==son[x])continue;
sous2(y,y);
}
}
```
这样的处理之后，发现重链上连续一段的点的轻儿子的编号都是连续的，只有重链的链顶不会和下面的点编号连续（当然这里不需要，因为并没有要我们处理重链上的点）。
之后就是对一条链进行处理，有挺多细节的：
* 从一条重链跳到上面的重链之后，该链顶不能被上面的重链修改轻儿子时修改。
* 从一条重链跳到上面的重链之后，还要修改跳重链之后的那个点的重儿子。
最后在求出$h_x$后，只需要考虑有多少对$(i,j)$，满足$lca_{i,j}=x$，当然，还要统计$c_i$产生的贡献，需计算有多少对$(i,j)$，满足$(i,j)$这条路径经过$x$。
```cpp
void chuli2(int l,int mi1,int mi2,int r,ll z){
if(l>r)return;
if(mi2<mi1)swap(mi1,mi2);
mi1=max(min(mi1,r+1),l-1);
mi2=max(min(mi2,r+1),l-1);
if(l<mi1)xds::change2(1,l,mi1-1,z,1,dfss2);
if(mi1<mi2-1)xds::change2(1,mi1+1,mi2-1,z,1,dfss2);
if(mi2<r)xds::change2(1,mi2+1,r,z,1,dfss2);
}
void chuli(int x,int y,ll z){
int prx=0,pry=0;
while(top[x]^top[y]){
if(de[top[x]]<de[top[y]])swap(x,y),swap(prx,pry);
int fx=top[x];
chuli2(st[fx],0,prx,en[x],z);
prx=dfs2[fx];
if(son[x])
xds::change2(1,dfs2[son[x]],dfs2[son[x]],z,1,dfss2);
x=fa[fx];
}
if(de[x]>de[y])swap(x,y);
chuli2(st[x],prx,pry,en[y],z);
if(son[y])
xds::change2(1,dfs2[son[y]],dfs2[son[y]],z,1,dfss2);
}
```
复杂度是$O(m\log^2n)$的但出题人没有卡树剖（大概），所以还跑的挺快的。