思路：

首先想到每次询问两个点后就从这两个点开始往上爬，沿路更新 dp 值即可。

#include
#define For(i,a,b) for(int i=a;i<=b;i++) #define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,v) memset(a,v,sizeof(a))
#define Freopen(file) \
freopen(file".in","r",stdin); \
freopen(file".out","w",stdout);
#define int long long
using namespace std;

const int N=2e5+5;

string CharlieVinnie;
int n,Q,a[N];
vector to[N];
int fa[N],dep[N];
int f[N][2],g[N][2];
set got[N];

void dfs(int u,int pa)
{
fa[u]=pa;
dep[u]=dep[pa]+1;

f\[u\]\[0\]=0;  
f\[u\]\[1\]=a\[u\];

int sz=to\[u\].size();  
For(i,0,sz-1){  
    int v=to\[u\]\[i\];  
    if(v==pa) continue;  
    dfs(v,u);

    f\[u\]\[0\]+=f\[v\]\[1\];  
    f\[u\]\[1\]+=min(f\[v\]\[0\],f\[v\]\[1\]);  
}  

}

int lca(int x,int y)
{
if(dep[x]dep[y]) x=fa[x];
while(x!=y){
x=fa[x];
y=fa[y];
}
return x;
}

int read()
{
char ch;
while((ch=getchar())<'0'||ch>'9') ;
int x=ch-'0';
while((ch=getchar())>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0';
return x;
}

signed main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);

// cin>>n>>Q>>CharlieVinnie;
n=read();
Q=read();
cin>>CharlieVinnie;

// For(i,1,n) cin>>a[i];
For(i,1,n) a[i]=read();

For(i,1,n-1){  
    int x,y;  
    x=read();  
    y=read();  

// cin>>x>>y;
to[x].push_back(y);
to[y].push_back(x);
got[x].insert(y);
got[y].insert(x);
}

dfs(1,0);

while(Q--){  
    int x,tx,y,ty;  

// cin>>x>>tx>>y>>ty;
x=read();
tx=read();
y=read();
ty=read();

    if(tx==0&&ty==0&&got\[x\].count(y)){  
        puts("-1");  
        continue;  
    }

    if(x==y&&tx!=ty){  
        puts("-1");  
        continue;  
    }

    if(dep\[x\]<dep\[y\]){  
        swap(x,y);  
        swap(tx,ty);  
    }

    int z=lca(x,y);

    if(x!=z&&y!=z){  
        g\[x\]\[tx\]=f\[x\]\[tx\];  
        g\[x\]\[tx^1\]=1e14;

        g\[y\]\[ty\]=f\[y\]\[ty\];  
        g\[y\]\[ty^1\]=1e14;

        while(fa\[x\]!=z){  
            int fx=fa\[x\];  
            g\[fx\]\[0\]=f\[fx\]\[0\]-f\[x\]\[1\]+g\[x\]\[1\];  
            g\[fx\]\[1\]=f\[fx\]\[1\]-min(f\[x\]\[0\],f\[x\]\[1\])+min(g\[x\]\[0\],g\[x\]\[1\]);  
            x=fx;  
        }

        while(fa\[y\]!=z){  
            int fy=fa\[y\];  
            g\[fy\]\[0\]=f\[fy\]\[0\]-f\[y\]\[1\]+g\[y\]\[1\];  
            g\[fy\]\[1\]=f\[fy\]\[1\]-min(f\[y\]\[0\],f\[y\]\[1\])+min(g\[y\]\[0\],g\[y\]\[1\]);  
            y=fy;  
        }

        g\[z\]\[0\]=f\[z\]\[0\]-f\[x\]\[1\]+g\[x\]\[1\]-f\[y\]\[1\]+g\[y\]\[1\];  
        g\[z\]\[1\]=f\[z\]\[1\]-min(f\[x\]\[0\],f\[x\]\[1\])+min(g\[x\]\[0\],g\[x\]\[1\])-min(f\[y\]\[0\],f\[y\]\[1\])+min(g\[y\]\[0\],g\[y\]\[1\]);  
    }  
    else{  
        g\[x\]\[tx\]=f\[x\]\[tx\];  
        g\[x\]\[tx^1\]=1e14;

        while(x!=z){  
            int fx=fa\[x\];  
            g\[fx\]\[0\]=f\[fx\]\[0\]-f\[x\]\[1\]+g\[x\]\[1\];  
            g\[fx\]\[1\]=f\[fx\]\[1\]-min(f\[x\]\[0\],f\[x\]\[1\])+min(g\[x\]\[0\],g\[x\]\[1\]);  
            x=fx;  
        }

        g\[z\]\[ty^1\]=1e14;  
    }

    while(z!=1){  
        int fz=fa\[z\];  
        g\[fz\]\[0\]=f\[fz\]\[0\]-f\[z\]\[1\]+g\[z\]\[1\];  
        g\[fz\]\[1\]=f\[fz\]\[1\]-min(f\[z\]\[0\],f\[z\]\[1\])+min(g\[z\]\[0\],g\[z\]\[1\]);  
        z=fz;  
    }

    cout<<g\[1\]\[0\]<<' '<<g\[1\]\[1\]<<endl;

    int ans=min(g\[1\]\[0\],g\[1\]\[1\]);

// if(ans!=1e14) cout<<ans<<endl;
// else cout<<-1<<endl;
printf("%lld\n",ans);
// if(ans!=1e14)
// else puts("-1");
}

return 0;  

}

然后就是怎么优化这一过程。

原来是想着直接暴力推公式找规律，然后就开始写。

发现如果令 $f[x][1] \geq f[x][0]$ 恒成立的话转移方程很漂亮，于是就“如果 $f[x][1] < f[x][0]$，也就是放人比不放还赚，于是不妨设放人，即 $f[x][0]=\min(f[x][0],f[x][1])$”

写完一测样例就错了。

原因是国王会要求在某个点不放人，所以“放人比不放还赚”不成立。

正确的思路是：

假设一开始 dp 出来的结果为 $f[x][0/1]$，询问过程中的新 dp 结果为 $g[x][0/1]$。

可以发现 $g[x][0/1]$ 到 $g[fx][0/1]$ 的转移可以表示为 $g[fx][0/1]=min(g[x][0]+c0,g[x][1]+c1)$，其中 $c0,c1$ 为一个表达式。

于是就用广义矩阵乘法优化，树上倍增的事情也解决了。

最终代码：

#include
#define For(i,a,b) for(int i=a;i<=b;i++) #define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,v) memset(a,v,sizeof(a))
#define Freopen(file) \
freopen(file".in","r",stdin); \
freopen(file".out","w",stdout);
#define int long long
using namespace std;

const int N=2e5+5;

// let df[x]=f[x][1]-f[x][0]
//
// d[x][0]=g[x][0]-f[x][0]
// d[x][1]=g[x][1]-f[x][1]
//
// d[fx][0]=d[x][1]=min(d[x][0]+inf,d[x][1]+0)
// d[fx][1]=min(f[x][0]+d[x][0],f[x][1]+d[x][1])-min(f[x][0],f[x][1])
// =min(d[x][0],(f[x][1]-f[x][0])+d[x][1])-min(0,f[x][1]-f[x][0])
// =min(d[x][0]-min(0,df[x]),d[x][1]+df[x]-min(0,df[x]))
//
// [ inf , -min(0,df[x]) ]
// [ 0 , df[x]-min(0,df[x]) ]

struct Matrix{
int a[2][2];

Matrix()  
{  
    clr(a,0x3f);  
}

friend Matrix operator\* (const Matrix& x,const Matrix& y)  
{  
    Matrix z;  
    For(i,0,1){  
        For(j,0,1){  
            For(k,0,1){  
                z.a\[i\]\[j\]=min(z.a\[i\]\[j\],x.a\[i\]\[k\]+y.a\[k\]\[j\]);  
            }  
        }  
    }  
    return z;  
}  

};

string CharlieVinnie;
int n,Q,a[N];
vector to[N];
int fa[N][21],dep[N];
int f[N][2],df[N];
Matrix mat[N][21];

int read()
{
char ch;
while((ch=getchar())<'0'||ch>'9') ;
int x=ch-'0';
while((ch=getchar())>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0';
return x;
}

void dfs(int u,int pa)
{
fa[u][0]=pa;
dep[u]=dep[pa]+1;

f\[u\]\[0\]=0;  
f\[u\]\[1\]=a\[u\];

int sz=to\[u\].size();  
For(i,0,sz-1){  
    int v=to\[u\]\[i\];  
    if(v==pa) continue;  
    dfs(v,u);

    f\[u\]\[0\]+=f\[v\]\[1\];  
    f\[u\]\[1\]+=min(f\[v\]\[0\],f\[v\]\[1\]);  
}

df\[u\]=f\[u\]\[1\]-f\[u\]\[0\];  

}

int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);

Rev(i,20,0){  
    if(dep\[fa\[x\]\[i\]\]>=dep\[y\]) x=fa\[x\]\[i\];  
}

if(x==y) return x;

Rev(i,20,0){  
    if(fa\[x\]\[i\]!=fa\[y\]\[i\]){  
        x=fa\[x\]\[i\];  
        y=fa\[y\]\[i\];  
    }  
}

return fa\[x\]\[0\];  

}

void moveup(int& x,int z,int& dx0,int& dx1)
{
Matrix res;
res.a[0][0]=res.a[1][1]=0;

Rev(k,20,0){  
    if(dep\[fa\[x\]\[k\]\]>dep\[z\]){  
        res=res\*mat\[x\]\[k\];  
        x=fa\[x\]\[k\];  
    }  
}

int t0=dx0,t1=dx1;  
dx0=min(t0+res.a\[0\]\[0\],t1+res.a\[1\]\[0\]);  
dx1=min(t0+res.a\[0\]\[1\],t1+res.a\[1\]\[1\]);  

}

signed main()
{
n=read();
Q=read();
cin>>CharlieVinnie;

For(i,1,n) a\[i\]=read();

For(i,1,n-1){  
    int x,y;  
    x=read();  
    y=read();  
    to\[x\].push\_back(y);  
    to\[y\].push\_back(x);  
}

dfs(1,0);

For(i,1,n){  
    mat\[i\]\[0\].a\[0\]\[0\]=1e14;  
    mat\[i\]\[0\].a\[0\]\[1\]=-min(0ll,df\[i\]);  
    mat\[i\]\[0\].a\[1\]\[0\]=0;  
    mat\[i\]\[0\].a\[1\]\[1\]=df\[i\]-min(0ll,df\[i\]);  
}

For(j,1,20){  
    For(i,1,n){  
        fa\[i\]\[j\]=fa\[fa\[i\]\[j-1\]\]\[j-1\];  
        mat\[i\]\[j\]=mat\[i\]\[j-1\]\*mat\[fa\[i\]\[j-1\]\]\[j-1\];  
    }  
}

while(Q--){  
    int x,tx,y,ty;  
    x=read();  
    tx=read();  
    y=read();  
    ty=read();

    if(dep\[x\]<dep\[y\]){  
        swap(x,y);  
        swap(tx,ty);  
    }

    if(tx==0&&ty==0&&fa\[x\]\[0\]==y){  
        puts("-1");  
        continue;  
    }

    if(x==y&&tx!=ty){  
        puts("-1");  
        continue;  
    }

    int z=lca(x,y);

    int dz0=0,dz1=0;

    if(y!=z){  
        int dx0=0,dx1=0;  
        if(tx==0) dx1=1e14;  
        else dx0=1e14;  
        moveup(x,z,dx0,dx1);

        int dy0=0,dy1=0;  
        if(ty==0) dy1=1e14;  
        else dy0=1e14;  
        moveup(y,z,dy0,dy1);

        dz0=dx1+dy1;  
        dz1=min(dx0-min(0ll,df\[x\]),dx1+df\[x\]-min(0ll,df\[x\]))+min(dy0-min(0ll,df\[y\]),dy1+df\[y\]-min(0ll,df\[y\]));  
    }  
    else{  
        int dx0=0,dx1=0;  
        if(tx==0) dx1=1e14;  
        else dx0=1e14;

        moveup(x,fa\[z\]\[0\],dx0,dx1);

        dz0=dx0;  
        dz1=dx1;

        if(ty==0) dz1=1e14;  
        else dz0=1e14;  
    }

    moveup(z,0,dz0,dz1);

    printf("%lld\\n",min(f\[1\]\[0\]+dz0,f\[1\]\[1\]+dz1));  
}

return 0;  

}