// 调试:各种u和v打错。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5, M = 2e5+5;
const ll INF = 1e15;
int n, m, u, v, w[N], x, y, dep[N], fa[N][20],
edgenum, Head[N], Next[M], vet[M]; ll dp[N][2], f[N][20][2][2], ans;
ll t0, t1, tu0, tu1, tv0, tv1;
inline int read() {
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') w = -w;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
inline void write1(ll x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write1(x / 10);
putchar(x % 10 + '0');
}
inline void add(int u, int v) {
Next[++edgenum] = Head[u];
Head[u] = edgenum;
vet[edgenum] = v;
}
void dfs1(int u, int F) {
dep[u] = dep[F] + 1, fa[u][0] = F;
for (int i=1; 1<<i<dep[u]; i++)
fa[u][i] = fa[fa[u][i-1]][i-1];
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (v == F) continue;
dfs1(v, u);
dp[u][0] += dp[v][1];
dp[u][1] += min(dp[v][0], dp[v][1]);
} dp[u][1] += w[u];
}
void dfs2(int u, int F) {
f[u][0][0][0] = INF;
f[u][0][0][1] = dp[F][1] - min(dp[u][0], dp[u][1]) + dp[u][0];
f[u][0][1][0] = dp[F][0];
f[u][0][1][1] = dp[F][1] - min(dp[u][0], dp[u][1]) + dp[u][1];
for (int i=1; 1<<i<dep[u]; i++) {
int _ = fa[u][i-1];
f[u][i][0][0] = min(f[u][i-1][0][0] + f[_][i-1][0][0] - dp[_][0],
f[u][i-1][0][1] + f[_][i-1][1][0] - dp[_][1]);
f[u][i][0][1] = min(f[u][i-1][0][0] + f[_][i-1][0][1] - dp[_][0],
f[u][i-1][0][1] + f[_][i-1][1][1] - dp[_][1]);
f[u][i][1][0] = min(f[u][i-1][1][0] + f[_][i-1][0][0] - dp[_][0],
f[u][i-1][1][1] + f[_][i-1][1][0] - dp[_][1]);
f[u][i][1][1] = min(f[u][i-1][1][0] + f[_][i-1][0][1] - dp[_][0],
f[u][i-1][1][1] + f[_][i-1][1][1] - dp[_][1]);
}
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (v ^ F) dfs2(v, u);
}
}
int main() {
freopen ("defense.in", "r", stdin);
freopen ("defense.out", "w", stdout);
scanf ("%d%d%*s", &n, &m);
for (int i=1; i<=n; i++)
w[i] = read();
for (int i=1; i<n; i++)
u = read(), v = read(),
add(u, v), add(v, u);
dfs1(1, 0), dfs2(1, 0);
while (m--) {
ans = INF;
u = read(), x = read(), v = read(), y = read();
if (dep[u] < dep[v]) swap(u, v), swap(x, y);
ll u0 = INF, u1 = INF, v0 = INF, v1 = INF, k = dep[u] - dep[v];
x ? u1 = dp[u][1] : u0 = dp[u][0], y ? v1 = dp[v][1] : v0 = dp[v][0];
for (int i=17; ~i; i--)
if (k & 1 << i) {
t0 = u0, t1 = u1;
u0 = min(t0 + f[u][i][0][0] - dp[u][0], t1 + f[u][i][1][0] - dp[u][1]);
u1 = min(t0 + f[u][i][0][1] - dp[u][0], t1 + f[u][i][1][1] - dp[u][1]);
u = fa[u][i];
}
if (u == v)
y ? u0 = INF : u1 = INF;
else {
for (int i=17; ~i; i--)
if (fa[u][i] ^ fa[v][i]) {
tu0 = u0, tu1 = u1, tv0 = v0, tv1 = v1;
u0 = min(tu0 + f[u][i][0][0] - dp[u][0], tu1 + f[u][i][1][0] - dp[u][1]);
u1 = min(tu0 + f[u][i][0][1] - dp[u][0], tu1 + f[u][i][1][1] - dp[u][1]);
v0 = min(tv0 + f[v][i][0][0] - dp[v][0], tv1 + f[v][i][1][0] - dp[v][1]);
v1 = min(tv0 + f[v][i][0][1] - dp[v][0], tv1 + f[v][i][1][1] - dp[v][1]);
u = fa[u][i], v = fa[v][i];
}
tu0 = u0, tu1 = u1, tv0 = v0, tv1 = v1;
u0 = dp[fa[u][0]][0] - dp[u][1] - dp[v][1] + tu1 + tv1;
u1 = dp[fa[u][0]][1] - min(dp[u][0], dp[u][1]) - min(dp[v][0], dp[v][1]) + min(tu0, tu1) + min(tv0, tv1);
u = fa[u][0];
}
if (u == 1) ans = min(u0, u1);
else {
for (int i=17; ~i; i--)
if (fa[u][i] && fa[u][i] != 1) {
t0 = u0, t1 = u1;
u0 = min(t0 + f[u][i][0][0] - dp[u][0], t1 + f[u][i][1][0] - dp[u][1]);
u1 = min(t0 + f[u][i][0][1] - dp[u][0], t1 + f[u][i][1][1] - dp[u][1]);
u = fa[u][i];
}
t0 = u0, t1 = u1;
u0 = dp[1][0] - dp[u][1] + t1;
u1 = dp[1][1] - min(dp[u][0], dp[u][1]) + min(t0, t1);
ans = min(u0, u1);
}
write1(ans >= INF - 1e10 ? -1 : ans), putchar('\n');
} return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 44.41 us | 72 KB | Accepted | Score: 4 | 显示更多 |
Testcase #2 | 44.45 us | 72 KB | Accepted | Score: 4 | 显示更多 |
Testcase #3 | 44.15 us | 72 KB | Accepted | Score: 4 | 显示更多 |
Testcase #4 | 42.86 us | 72 KB | Accepted | Score: 4 | 显示更多 |
Testcase #5 | 89.85 us | 152 KB | Accepted | Score: 4 | 显示更多 |
Testcase #6 | 91.33 us | 152 KB | Accepted | Score: 4 | 显示更多 |
Testcase #7 | 95.09 us | 144 KB | Accepted | Score: 4 | 显示更多 |
Testcase #8 | 1.125 ms | 1 MB + 700 KB | Accepted | Score: 4 | 显示更多 |
Testcase #9 | 1.125 ms | 1 MB + 700 KB | Accepted | Score: 4 | 显示更多 |
Testcase #10 | 1.088 ms | 1 MB + 612 KB | Accepted | Score: 4 | 显示更多 |
Testcase #11 | 1.085 ms | 1 MB + 612 KB | Accepted | Score: 4 | 显示更多 |
Testcase #12 | 80.626 ms | 81 MB + 588 KB | Accepted | Score: 4 | 显示更多 |
Testcase #13 | 80.571 ms | 81 MB + 588 KB | Accepted | Score: 4 | 显示更多 |
Testcase #14 | 91.892 ms | 81 MB + 392 KB | Accepted | Score: 4 | 显示更多 |
Testcase #15 | 91.912 ms | 81 MB + 396 KB | Accepted | Score: 4 | 显示更多 |
Testcase #16 | 91.982 ms | 81 MB + 396 KB | Accepted | Score: 4 | 显示更多 |
Testcase #17 | 136.917 ms | 81 MB + 588 KB | Accepted | Score: 4 | 显示更多 |
Testcase #18 | 55.401 ms | 73 MB + 968 KB | Accepted | Score: 4 | 显示更多 |
Testcase #19 | 55.337 ms | 73 MB + 968 KB | Accepted | Score: 4 | 显示更多 |
Testcase #20 | 73.632 ms | 77 MB + 388 KB | Accepted | Score: 4 | 显示更多 |
Testcase #21 | 73.812 ms | 77 MB + 388 KB | Accepted | Score: 4 | 显示更多 |
Testcase #22 | 85.356 ms | 77 MB + 192 KB | Accepted | Score: 4 | 显示更多 |
Testcase #23 | 119.929 ms | 77 MB + 384 KB | Accepted | Score: 4 | 显示更多 |
Testcase #24 | 119.981 ms | 77 MB + 388 KB | Accepted | Score: 4 | 显示更多 |
Testcase #25 | 119.748 ms | 77 MB + 400 KB | Accepted | Score: 4 | 显示更多 |