NOIP2018提高组D2T3
ddp虽然好想，但是码量有点大（其实是我不会），因此本文用倍增优化树形DP来解决本题。
题意分析
给一棵树染色，每个节点染色需要一定的花费，要求相邻两个节点至少要有一个被染色，给出一些限制条件，求满足每个限制条件的最小花费为多少。
思路分析
首先判断无解的情况。显然，只有当$a,b$互为父子关系（这里的父子关系指的是严格相邻），且$x,y$都为0时才无解，其它情况都可以通过多染色来解。
很容易想到树形DP，那么具体状态如何设置呢？对于每个限制条件给出的两个点$a,b$，答案可以由四个部分构成：以$a$为根的子树，以$b$为根的子树，以$lca(a,b)$为根的子树减去以$a$为根的子树和以$b$为根的子树，整棵树减去以$lca(a,b)$为根的子树。因为对$a,b$的限制会影响到从$a$到$b$的链上的染色状态，因此拆成这四部分，这四部分互相不影响。
显然，对$a,b$的限制只会影响到以$lca(a,b)$为根的子树减去以$a$为根的子树和以$b$为根的子树的答案，因此，我们可以将其它三个部分的答案预处理出来，然后DP处理剩下的这一部分。
因此状态可以设定为：$f1[i][1/0]$表示以$i$为根的子树当$i$染色/不染色时的最小花费，$f2[i][1/0]$表示整棵树减去以$i$为根的子树当$i$染色/不染色时的最小花费，$dp[i][1/0][1/0]$表示以$lca(a,b)$为根的子树减去以$i$为根的子树当$i$染色/不染色及$i$的父节点染色/不染色（按顺序对应第二维和第三维）时的最小花费。这样，我们就可以从$a,b$一直DP到$lca(a,b)$处计算答案了。特别地，当当前状态无解时，值设定为INF。
但是这样的时间复杂度显然太大。类似这样在树上多次向上的DP，可以想到利用树上倍增进行优化。更改一下$dp$数组的定义，$dp[i][j][0/1][0/1]$表示以$i$的$2^j$辈祖先为根的子树减去以$i$为根的子树当$i$染色/不染色及$i$的$2^j$辈祖先染色/不染色时的最小花费。
接下来的问题就是如何进行DP了。利用上面的三个数组，我们可以倍增地DP到$lca(a,b)$处。首先，我们先将$a,b$中深度较大的一个向上倍增DP，直到$a,b$处于同一深度；此时若$a=b$，说明它们原本具有祖先与后代的关系，直接输出答案；否则就将$a,b$同时向上倍增DP，直到$lca(a,b)$的子节点处，然后进行最后的处理，输出答案。DP的时候，枚举状态转移即可。
整理一下思路：
1. 预处理出$f1,f2,dp$三个数组
1. 将$a,b$中深度较大的一个向上倍增直到$a,b$处于同一深度
1. 判断此时$a,b$是否相等，如果是，直接输出答案；否则继续向上倍增
1. 将$a,b$倍增到$lca(a,b)$的子节点处，进行最后的处理，输出答案
接下来将对具体的实现步骤进行讲解。
具体实现
1. 预处理$f1$数组
很基础的一个树形DP，类似于没有上司的舞会，就不再赘述了。同时也处理出深度数组$d$和倍增祖先数组$f$。
void dfs1(int fa,int x)
{
f[x][]=fa,d[x]=d[fa]+,f1[x][]=p[x];
for(int i=head[x],y;i;i=Next[i])
if(fa!=(y=ver[i]))
{
dfs1(x,y);
f1[x][]+=f1[y][];
f1[x][]+=min(f1[y][],f1[y][]);
}
}
2. 预处理$f2$数组
当$i$不染色时，$i$的父亲节点必须染色，因此答案就是当$i$的父亲染色时，整棵树减去以$i$的父亲为根的子树的答案，加上以$i$的兄弟（即父亲相同的节点）为根的子树为根的答案。回顾递推$f1$数组的过程，以$i$的兄弟为根的子树为根的答案相当于统计时少了$i$的统计，即$f1[fa][1]-min(f1[i][0],f1[i][1])$，其中$fa$表示$i$的父亲。
当$i$染色时，$i$的父亲染不染色都可以，$i$的父亲染色时和$i$不染色时的答案是一样的，不染色时同理统计，相当于统计$f1$时撤销了对$i$的统计。
void dfs2(int x)
{
for(int i=head[x],y;i;i=Next[i])
if(f[x][]!=(y=ver[i]))
{
f2[y][]=f2[x][]+f1[x][]-min(f1[y][],f1[y][]);
f2[y][]=min(f2[y][],f2[x][]+f1[x][]-f1[y][]);
dfs2(y);
}
}
3. 预处理$dp$数组
先将$dp$数组初始化为无限大。首先先处理dp初值，即$j=0$的情况。
显然，当$i$和$i$的父节点都不染色时，是无解的，不动它；当$i$的父亲染色时，$i$染不染色都可以，因此答案和上面$f2[i][0]$的转移类似，只是不用加上剩下的部分；当$i$的父亲不染色时，$i$必须染色，转移类似，就不再赘述了。
然后就是倍增地处理，对于第$2^j$辈祖先，枚举第$2^{j-1}$辈祖先及$i$和第$2^j$辈祖先的状态进行转移。转移思想也基本类似。
void pre()
{
memset(dp,0x3f3f,sizeof(dp));
dfs1(,),dfs2();//先处理f1,f2数组
for(int i=;i<=n;i++)
{
dp[i][][][]=dp[i][][][]=f1[f[i][]][]-min(f1[i][],f1[i][]);//父节点染色
dp[i][][][]=f1[f[i][]][]-f1[i][];//父节点不染色
}
for(int j=;j<=;j++)
for(int i=;i<=n;i++)
{
int fa=f[i][j-];
f[i][j]=f[fa][j-];//先计算祖先
for(int x=;x<;x++)//枚举当前点的状态
for(int y=;y<;y++)//枚举第2^j辈祖先的状态
for(int z=;z<;z++)//枚举第2^(j-1)辈祖先的状态
dp[i][j][x][y]=min(dp[i][j][x][y],dp[i][j-][x][z]+dp[fa][j-][z][y]);
}
}
接下来对询问的处理进行讲解。
4. 将$a,b$中深度较大的一个上移，直到$a,b$处于同一深度
我们可以先令深度较大的一个为$a$，若不是，则交换。
定义四个数组$ansa[0/1],ansb[0/1],nowa[0/1],nowb[0/1]$，分别代表$a,b$不染色/染色时最终的答案和当前的答案。具体地说，这个答案就是以当前倍增到的这个祖先为根的子树的答案。
处理之前，因为限制条件，将$a,b$点的另一个状态初始化为INF。
转移的时候，一样地，枚举中间点的状态进行转移。每次转移前，将$nowa$数组初始化为INF；每次转移后，将$nowa$数组的值赋给$ansa$数组，然后将$a$上移。
上移之后，若$a=b$，则直接返回答案。因为当前点是$b$，而限制条件对$b$起作用，因此答案就是$ansa[y]+f2[a][y]$，即以$b$为根的子树的答案加上剩下部分的答案。
if(d[a]<d[b])
swap(a,b),swap(x,y);//令x为深度较大的点
ansa[-x]=ansb[-y]=INF;
ansa[x]=f1[a][x],ansb[y]=f1[b][y];//初值
for(int j=;j>=;j--)//倍增
if(d[f[a][j]]>=d[b])//上移到同一深度
{
nowa[]=nowa[]=INF;//初始化
for(int u=;u<;u++)//枚举2^j辈祖先的状态
for(int v=;v<;v++)//枚举当前点的状态
nowa[u]=min(nowa[u],ansa[v]+dp[a][j][v][u]);
ansa[]=nowa[],ansa[]=nowa[],a=f[a][j];//数组值转移
}
if(a==b)
return ansa[y]+f2[a][y];//相等直接返回
5. 将$a,b$同时上移到$lca(a,b)$的子节点处
与上一步类似，只是同时上移，就不赘述了。
for(int j=;j>=;j--)
if(f[a][j]!=f[b][j])
{
nowa[]=nowa[]=nowb[]=nowb[]=INF;
for(int u=;u<;u++)
for(int v=;v<;v++)
{
nowa[u]=min(nowa[u],ansa[v]+dp[a][j][v][u]);
nowb[u]=min(nowb[u],ansb[v]+dp[b][j][v][u]);
}
ansa[]=nowa[],ansa[]=nowa[],ansb[]=nowb[],ansb[]=nowb[],a=f[a][j],b=f[b][j];
}
6. 对$a,b,lca(a,b)$的状态进行枚举，进行最后的处理
还是一样的思想，若$lca(a,b)$染色，则$a,b$染不染色都行；否则$a,b$必须染色。式子看起来很长，实际上只是之前的式子多了一个节点罢了。
int fa=f[a][];
ans0=f1[fa][]-f1[a][]-f1[b][]+f2[fa][]+ansa[]+ansb[];//lca(a,b)不染色
ans1=f1[fa][]-min(f1[a][],f1[a][])-min(f1[b][],f1[b][])+f2[fa][]+min(ansa[],ansa[])+min(ansb[],ansb[]);//lca(a,b)染色
return min(ans0,ans1);
完结撒花~
（所以对于正解来说type并没有什么用，不过在考场上打不出正解的时候确实是拿部分分的一个好助手）
------------
最后奉上完整代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e5,M=3e5,L=;
const ll INF=1e17;
int n,m,tot;
int p[N],d[N],f[N][L];
int head[N],ver[*M],Next[*M];
ll ans0,ans1;
ll nowa[],nowb[],ansa[],ansb[],f1[N][],f2[N][],dp[N][L][][];
string tp;
void add(int x,int y)
{
ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
ver[++tot]=x,Next[tot]=head[y],head[y]=tot;
}
void dfs1(int fa,int x)
{
f[x][]=fa,d[x]=d[fa]+,f1[x][]=p[x];
for(int i=head[x],y;i;i=Next[i])
if(fa!=(y=ver[i]))
{
dfs1(x,y);
f1[x][]+=f1[y][];
f1[x][]+=min(f1[y][],f1[y][]);
}
}//1. 预处理 $f1$ 数组
void dfs2(int x)
{
for(int i=head[x],y;i;i=Next[i])
if(f[x][]!=(y=ver[i]))
{
f2[y][]=f2[x][]+f1[x][]-min(f1[y][],f1[y][]);
f2[y][]=min(f2[y][],f2[x][]+f1[x][]-f1[y][]);
dfs2(y);
}
}//2. 预处理 $f2$ 数组
void pre()
{
memset(dp,0x3f3f,sizeof(dp));
dfs1(,),dfs2();
for(int i=;i<=n;i++)
{
dp[i][][][]=dp[i][][][]=f1[f[i][]][]-min(f1[i][],f1[i][]);
dp[i][][][]=f1[f[i][]][]-f1[i][];
}
for(int j=;j<=;j++)
for(int i=;i<=n;i++)
{
int fa=f[i][j-];
f[i][j]=f[fa][j-];
for(int x=;x<;x++)
for(int y=;y<;y++)
for(int z=;z<;z++)
dp[i][j][x][y]=min(dp[i][j][x][y],dp[i][j-][x][z]+dp[fa][j-][z][y]);
}
}//3. 预处理 $dp$ 数组
bool check(int a,int x,int b,int y)
{
return !x && !y &&(f[a][]==b || f[b][]==a);
}
ll ask(int a,int x,int b,int y)
{
if(d[a]<d[b])
swap(a,b),swap(x,y);
ansa[-x]=ansb[-y]=INF;
ansa[x]=f1[a][x],ansb[y]=f1[b][y];
for(int j=;j>=;j--)
if(d[f[a][j]]>=d[b])
{
nowa[]=nowa[]=INF;
for(int u=;u<;u++)
for(int v=;v<;v++)
nowa[u]=min(nowa[u],ansa[v]+dp[a][j][v][u]);
ansa[]=nowa[],ansa[]=nowa[],a=f[a][j];
}
if(a==b)
return ansa[y]+f2[a][y];//4. 将 $a,b$ 中深度较大的一个上移，直到 $a,b$ 处于同一深度
for(int j=;j>=;j--)
if(f[a][j]!=f[b][j])
{
nowa[]=nowa[]=nowb[]=nowb[]=INF;
for(int u=;u<;u++)
for(int v=;v<;v++)
{
nowa[u]=min(nowa[u],ansa[v]+dp[a][j][v][u]);
nowb[u]=min(nowb[u],ansb[v]+dp[b][j][v][u]);
}
ansa[]=nowa[],ansa[]=nowa[],ansb[]=nowb[],ansb[]=nowb[],a=f[a][j],b=f[b][j];
}//5. 将 $a,b$ 同时上移到 $lca(a,b)$ 的子节点处
int fa=f[a][];
ans0=f1[fa][]-f1[a][]-f1[b][]+f2[fa][]+ansa[]+ansb[];
ans1=f1[fa][]-min(f1[a][],f1[a][])-min(f1[b][],f1[b][])+f2[fa][]+min(ansa[],ansa[])+min(ansb[],ansb[]);
return min(ans0,ans1);//6. 对 $a,b,lca(a,b)$ 的状态进行枚举，进行最后的处理
}
int main()
{
scanf("%d%d",&n,&m);cin>>tp;
for(int i=;i<=n;i++)
scanf("%d",&p[i]);
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
pre();
for(int i=,a,x,b,y;i<=m;i++)
{
scanf("%d%d%d%d",&a,&x,&b,&y);
if(check(a,x,b,y))
{
puts("-1");
continue;
}
printf("%lld\n",ask(a,x,b,y));
}
return ;
}