保卫王国（NOIP-2018）（倍增Dp预处理，动态查询）

题目

Luogu-传送门
题目大意：给你一棵树进行染色，$i$ 号节点染色费用为 $p_i$，要求相邻两个节点必须有一个要染色，现在给出 $m$ 个询问，分别要求两个节点必须(染|不染)色，对于每个询问求出最小染色代价
数据范围：
$1\le n,m\le 100000,1\le p_i\le 100000$

思路

首先我在考场上想出了 $dp$ 44分的做法，对于每次询问单独重新计算：
$$定义f[u][0|1]:以u为根子树且u节点(染|不染)时该子树最小代价$$
转移也很简单：
①当 $u$ 为叶节点时：
$$\begin{gathered} f[u][0]=\{\begin{array}{l}0(u点无要求|要求不选)\\ INF(u点要求选)\end{array} \\ f[u][1]=\{\begin{array}{l}{p}_u(u点无要求|要求选)\\ INF(u点要求不选)\end{array} \end{gathered}$$
②当 $u$ 为非叶节点时：
$$\begin{gathered} f[u][0]=\sum _{v\in so{n}_u}f[v][1] \\ f[u][1]=\sum _{v\in so{n}_u}min(f[v][0],f[v][1]) \end{gathered}$$
最终答案为: $min(f[1][0],f[1][1])$(从1开始DFS)
然后我们发现其实每次我们多做了许多次dp，真正每次更新的 $dp$ 值只有这些：

如果你一开始就Dp,然后动态更新好像部分分会多点，但仍然是 $O(n^2)$的复杂度，所以我们考虑加快Dp过程，而像这种有$Lca$出现又没有更新树的一般考虑用倍增
怎么考虑呢？我们想啊,考虑一下这种定义：
$f[i][j][0|1][0|1]:i节点(染|不染),i的2^j祖先节点(染|不染)时i的2^j祖先的最优Dp值$

但是我们发现似乎无法进行合并,因为当由 $2^{(}j?1)$ 转移 $2^j$ 有包含冲突
于是我们考虑去除 $u节点所在子树$ 的影响：

$f[i][j][0|1][0|1]:i$节点(染|不染),i的$2^j$祖先节点(染|不染)时i的$2^j$祖先的最优Dp值,即在整个祖先的子树中减去u的子树的影响.

那么这个信息就可以进行合并了,因为转移时正好接上
然后我们考虑爬树时怎么爬,这一点我想了很久…

因为可能加上这棵子树时会改变f数组的决策
那么我们爬树时用两种状态一起爬就是了(该节点染|不染)
注意：
1.f数组的初始化不要在DFS中弄，因为此时g还没更新完
2.倍增爬树时j不要枚举反了
3.LL注意一下
4,v是Lca时注意一下
发现用动态 $Dp$ 理解更好，因为发现 $f$ 的定义不太好理解：
显然有：
$$\left[\begin{array}{c}{f}_{v,0},f_{v,1}\end{array}\right]?\left[\begin{array}{c}{w}_{u,0},w_{u,1}\\ \infty ,w_{u,1}\end{array}\right]=\left[\begin{array}{c}{f}_{u,0},f_{u,1}\end{array}\right]$$
记一开始矩阵为 $P$，那么 $dp$ 本质就是：
$$P?M_{f{a}_u}?M_{f{a}_{f{a}_u}}?...$$
由于加法对 $min$ 有分配律，所以这个矩阵乘法有结合律，我们可以利用维护后面的矩阵合并之后的模样
然后 $f$ 本质是合并矩阵进行倍增转移

代码

#include<set> 
#include<map> 
#include<stack> 
#include<ctime> 
#include<cstdio> 
#include<queue> 
#include<cmath> 
#include<vector> 
#include<cstring> 
#include<climits> 
#include<iostream> 
#include<algorithm> 
using namespace std;   
#define LL long long 
int read(){
       int f=1,x=0;char c=getchar();   while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}   while('0'<=c&&c<='9'){
    x=x*10+c-'0';c=getchar();}   return f*x;   
}  
#define MAXN 100000 
#define INF 214748364700ll
int n,m,p[MAXN+5];  
vector<int> G[MAXN+5];  
inline void Addedge(int u,int v){
      G[u].push_back(v);  G[v].push_back(u);  return ;  
}  
int dep[MAXN+5],fa[MAXN+5][20];  
LL f[MAXN+5][20][2][2],g[MAXN+5][2];  
void DFS(int u){
    //f[i][j][0|1][0|1] int siz=G[u].size();  g[u][1]=p[u];  dep[u]=dep[fa[u][0]]+1;  for(int i=0;i<siz;i++){
      int v=G[u][i];  if(v==fa[u][0]) continue;  fa[v][0]=u;  DFS(v);  g[u][0]+=g[v][1];  g[u][1]+=min(g[v][0],g[v][1]);  }//!!return ;  
} 
void Prepare(){
     /* puts(""); for(int i=1;i<=n;i++) printf("%lld %lld\n",g[i][0],g[i][1]); */for(int i=1;i<=n;i++){
     f[i][0][0][0]=INF,f[i][0][1][0]=g[fa[i][0]][0]-g[i][1];  f[i][0][0][1]=f[i][0][1][1]=g[fa[i][0]][1]-min(g[i][0],g[i][1]); //printf("%lld %lld %lld %lld\n",f[i][j][0][0],f[i][j][0][1],f[i][j][1][0],f[i][j][1][1]); } for(int j=1;j<=int(log2(n));j++)  for(int i=1;i<=n;i++){
      int k=fa[i][j-1];  fa[i][j]=fa[fa[i][j-1]][j-1];  f[i][j][0][0]=min(f[i][j-1][0][0]+f[k][j-1][0][0],f[i][j-1][0][1]+f[k][j-1][1][0]); f[i][j][0][1]=min(f[i][j-1][0][0]+f[k][j-1][0][1],f[i][j-1][0][1]+f[k][j-1][1][1]); f[i][j][1][0]=min(f[i][j-1][1][0]+f[k][j-1][0][0],f[i][j-1][1][1]+f[k][j-1][1][0]); f[i][j][1][1]=min(f[i][j-1][1][0]+f[k][j-1][0][1],f[i][j-1][1][1]+f[k][j-1][1][1]); // printf("%lld %lld %lld %lld\n",f[i][j][0][0],f[i][j][0][1],f[i][j][1][0],f[i][j][1][1]); }  return ;  
}  
LL LCA(int u,int x,int v,int y){
      if(dep[u]<dep[v]) swap(u,v),swap(x,y);  int d=dep[u]-dep[v];  LL Lca,u0=INF,u1=INF,v0=INF,v1=INF,l0=INF,l1=INF;  !x?u0=g[u][0]:u1=g[u][1];  !y?v0=g[v][0]:v1=g[v][1];  //puts(""); for(int j=0;j<=int(log2(d));j++)  if(d&(1<<j)){
      LL t0=u0,t1=u1;  u0=min(t0+f[u][j][0][0],t1+f[u][j][1][0]);  u1=min(t0+f[u][j][0][1],t1+f[u][j][1][1]);  u=fa[u][j]; //printf("%lld %lld\n",u0,u1); } //printf("%d %d*\n",u,v); if(u==v) Lca=u,!y?l0=u0:l1=u1;  else{
      for(int j=int(log2(n));j>=0;j--)//!!if(fa[u][j]!=fa[v][j]){
    LL t0=u0,t1=u1;  u0=min(t0+f[u][j][0][0],t1+f[u][j][1][0]);  u1=min(t0+f[u][j][0][1],t1+f[u][j][1][1]);  t0=v0,t1=v1;  v0=min(t0+f[v][j][0][0],t1+f[v][j][1][0]);  v1=min(t0+f[v][j][0][1],t1+f[v][j][1][1]);  u=fa[u][j],v=fa[v][j];  }  Lca=fa[u][0];  l0=g[Lca][0]-g[u][1]-g[v][1]+u1+v1;  l1=g[Lca][1]-min(g[u][0],g[u][1])-min(g[v][0],g[v][1])+min(u0,u1)+min(v0,v1);  }  //printf("***%lld %lld %lld\n",Lca,l0,l1); d=dep[Lca]-dep[1];for(int j=0;j<=int(log2(d));j++)if(d&(1<<j)){
    LL t0=l0,t1=l1;l0=min(t0+f[Lca][j][0][0],t1+f[Lca][j][1][0]);l1=min(t0+f[Lca][j][0][1],t1+f[Lca][j][1][1]);Lca=fa[Lca][j];}LL ret=min(l0,l1);return ret>=INF?-1:ret;
}
int main(){
    char Re[5];n=read(),m=read(),scanf("%s",Re);for(int i=1;i<=n;i++)p[i]=read();for(int i=1;i<n;i++){
    int u=read(),v=read();Addedge(u,v);}DFS(1);Prepare();for(int i=1;i<=m;i++){
    int a=read(),x=read(),b=read(),y=read();printf("%lld\n",LCA(a,x,b,y));}return 0;
}