代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

template<typename T,int height,int width>
struct matrix{
    T num[height][width];
    
    T* operator [](int Line)
      { return num[Line]; }
    
    matrix() {  
        for( int i = 0;i < height;i ++ )
            for( int j = 0;j < width;j ++ )
              { num[i][j] = T(); }
    }
    
    template<int widthN>
    matrix<T,height,widthN> operator *
        ( matrix<T,width,widthN> From ) {
            matrix<T,height,widthN> rt;
            for(int i = 0;i < height;i ++)
                for(int j = 0;j < widthN;j ++)
                    for(int k = 0;k < width;k ++)
                      { rt[i][j] = rt[i][j] + num[i][k] * From.num[k][j]; }
            return rt;
        }
        
    void Debug(){
        putchar('\n');
        for( int i = 0;i < height;i ++ )
          { putchar('[');
            for( int j = 0;j < width;j ++ )
                { cout << num[i][j].x << " "; }
            putchar(']');putchar('\n'); }
    }
};

struct VDP{
    LL x;
    VDP() : x( 1e18 ) {}
    VDP(LL _x) : x(_x) {}
    VDP operator +(const VDP& From) const
      { return VDP( min( x,From.x ) ); }
    VDP operator *(const VDP& From) const
      { return VDP( x + From.x ); }
    VDP& operator +=(const LL s) 
      { x += s;return *this; }
    bool operator <(const VDP& From)const
      { return x < From.x; }
};
typedef matrix< VDP,2,2 > dat;

int n,m;
vector<int>to[100005];
LL  data[100005];
LL  dp[100005][2];
int deep[100005];
int fa[100005][20];
dat dt[100005][20];

void dfs(int now,int last){
    deep[now] = deep[last] + 1;
    dp[now][1] = data[now];
    for( auto next : to[now] )if( next != last )
      { dfs( next,now ); fa[next][0] = now;
        dp[now][0] += dp[next][1]; 
        dp[now][1] += min( dp[next][0],dp[next][1] ); }
    for( auto next : to[now] )if( next != last )
      { dt[next][0][1][0] = dp[now][0] - dp[next][1]; 
        dt[next][0][0][1] = dt[next][0][1][1] = dp[now][1] 
          - min( dp[next][0],dp[next][1] ); }
}

void init(){
    for(int i = 1;i <= 19;i ++)
        for(int j = 1;j <= n;j ++)
          { fa[j][i] = fa[ fa[j][i - 1] ][i - 1];
            dt[j][i] = dt[j][i - 1] * dt[ fa[j][i - 1] ][i - 1]; }
}

int main(){
    string op;cin >> n >> m >> op;
    for(int i = 1;i <= n;i ++)cin >> data[i];
    for(int i = 1;i <  n;i ++)
      { int u,v;cin >> u >> v; 
        to[u].push_back(v);
        to[v].push_back(u); }
    dfs( 1,1 );init();
    while( m -- ){
        int a,b,c,d;cin >> a >> b >> c >> d;
        matrix< VDP,1,2 >A;A[0][0] = dp[a][0];A[0][1] = dp[a][1];
        matrix< VDP,1,2 >B;B[0][0] = dp[c][0];B[0][1] = dp[c][1];
        A[0][!b] = 1e18;B[0][!d] = 1e18;
        if( deep[a] < deep[c] )swap( a,c ),swap( A,B );
        if( deep[a] == deep[c] )
          { B = B * dt[c][0];c = fa[c][0]; }
        for( int i = 19;~i;i -- )if( deep[ fa[a][i] ] > deep[c] )
          { A = A * dt[a][i];a = fa[a][i]; }
        for( int i = 19;~i;i -- )if( fa[ fa[a][i] ][0] ^ fa[c][i] )
          { A = A * dt[a][i];a = fa[a][i];
            B = B * dt[c][i];c = fa[c][i]; }
        if( c != fa[a][0] )
          { A = A * dt[a][0];a = fa[a][0];
            B = B * dt[c][0];c = fa[c][0]; }
        B[0][0].x = B[0][0].x - dp[a][1] + A[0][1].x;
        B[0][1].x = B[0][1].x - min( dp[a][0],dp[a][1] ) + min( A[0][0],A[0][1] ).x;
        for( int i =19;~i;i -- )if( fa[c][i] )
          { B = B * dt[c][i];c = fa[c][i]; }
        LL ans = min( B[0][0],B[0][1] ).x;
        if( ans > 1e15 )cout << "-1\n";
        else cout << ans << "\n";
    }
    return 0;
}

评测结果