#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;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 7.662 ms | 63 MB + 396 KB | Accepted | Score: 4 | 显示更多 |
Testcase #2 | 7.258 ms | 63 MB + 396 KB | Accepted | Score: 4 | 显示更多 |
Testcase #3 | 7.565 ms | 63 MB + 396 KB | Accepted | Score: 4 | 显示更多 |
Testcase #4 | 7.707 ms | 63 MB + 396 KB | Accepted | Score: 4 | 显示更多 |
Testcase #5 | 7.624 ms | 63 MB + 416 KB | Accepted | Score: 4 | 显示更多 |
Testcase #6 | 7.466 ms | 63 MB + 416 KB | Accepted | Score: 4 | 显示更多 |
Testcase #7 | 7.481 ms | 63 MB + 412 KB | Accepted | Score: 4 | 显示更多 |
Testcase #8 | 10.575 ms | 63 MB + 868 KB | Accepted | Score: 4 | 显示更多 |
Testcase #9 | 10.332 ms | 63 MB + 868 KB | Accepted | Score: 4 | 显示更多 |
Testcase #10 | 10.142 ms | 63 MB + 768 KB | Accepted | Score: 4 | 显示更多 |
Testcase #11 | 10.557 ms | 63 MB + 768 KB | Accepted | Score: 4 | 显示更多 |
Testcase #12 | 210.541 ms | 86 MB + 940 KB | Accepted | Score: 4 | 显示更多 |
Testcase #13 | 210.429 ms | 86 MB + 940 KB | Accepted | Score: 4 | 显示更多 |
Testcase #14 | 226.867 ms | 86 MB + 744 KB | Accepted | Score: 4 | 显示更多 |
Testcase #15 | 227.211 ms | 86 MB + 748 KB | Accepted | Score: 4 | 显示更多 |
Testcase #16 | 227.395 ms | 86 MB + 748 KB | Accepted | Score: 4 | 显示更多 |
Testcase #17 | 279.242 ms | 86 MB + 940 KB | Accepted | Score: 4 | 显示更多 |
Testcase #18 | 201.094 ms | 77 MB + 892 KB | Accepted | Score: 4 | 显示更多 |
Testcase #19 | 201.079 ms | 77 MB + 892 KB | Accepted | Score: 4 | 显示更多 |
Testcase #20 | 202.321 ms | 81 MB + 952 KB | Accepted | Score: 4 | 显示更多 |
Testcase #21 | 202.267 ms | 81 MB + 952 KB | Accepted | Score: 4 | 显示更多 |
Testcase #22 | 215.945 ms | 81 MB + 756 KB | Accepted | Score: 4 | 显示更多 |
Testcase #23 | 259.312 ms | 81 MB + 948 KB | Accepted | Score: 4 | 显示更多 |
Testcase #24 | 259.878 ms | 81 MB + 952 KB | Accepted | Score: 4 | 显示更多 |
Testcase #25 | 259.382 ms | 81 MB + 964 KB | Accepted | Score: 4 | 显示更多 |