嘟嘟嘟
由于一些知道的人所知道的，不知道的人所不知道的原因，我来发NOIP2018day2T3的题解了。
（好像我只是个搬运工……）
这题真可以叫做NOIplus了，跟其他几道比较水的题果然不一样，无论代码量还是思维难度都有一个更高的层次。
我是看了zhoutb的题解的。而且抄了他代码（还没抄对），所以这里直接推荐各位看luogu的题解吧。
关于这个倍增数组的预处理，实际上只用考虑为父亲结点的时候该怎么办（就是裸dp）。而对于\(2 ^ i (i > 0)\)的倍增部分，只用枚举u和祖先的状态转移即可。
（代码中唯一的不同就是把zhoutb的非递归改成树上递归的）
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<set>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const ll INF = 1e14;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
#define pr pair<int, int>
#define mp make_pair
int n, m, a[maxn];
set<pr> s;
struct Edge
{
int nxt, to;
}e[maxn << 1];
int head[maxn], ecnt = -1;
In void addEdge(int x, int y)
{
e[++ecnt] = (Edge){head[x], y};
head[x] = ecnt;
}
ll f[maxn][2];
In void dfs1(int now, int _f)
{
f[now][1] = a[now];
for(int i = head[now], v; i != -1; i = e[i].nxt)
{
if((v = e[i].to) == _f) continue;
dfs1(v, now);
f[now][0] += f[v][1];
f[now][1] += min(f[v][0], f[v][1]);
}
}
int dep[maxn], fa[N + 2][maxn];
ll g[maxn][2];
In void dfs2(int now, int _f)
{
for(int i = 1; (1 << i) <= dep[now]; ++i) //不能放在dfs3处理
fa[i][now] = fa[i - 1][fa[i - 1][now]];
for(int i = head[now], v; i != -1; i = e[i].nxt)
{
if((v = e[i].to) == _f) continue;
dep[v] = dep[now] + 1;
fa[0][v] = now;
g[v][0] = g[now][1] + f[now][1] - min(f[v][0], f[v][1]);
g[v][1] = min(g[v][0], g[now][0] + f[now][0] - f[v][1]);
dfs2(v, now);
}
}
const int N = 17;
ll dp[2][2][N + 2][maxn]; //now 0/1, 2^i 0/1
In void dfs3(int now, int _f)
{
dp[0][0][0][now] = INF;
dp[1][0][0][now] = f[fa[0][now]][0] - f[now][1];
dp[0][1][0][now] = f[fa[0][now]][1] - min(f[now][0], f[now][1]);
dp[1][1][0][now] = f[fa[0][now]][1] - min(f[now][0], f[now][1]);
for(int i = 1; (1 << i) <= dep[now]; ++i)
for(int x = 0; x < 2; ++x)
for(int y = 0; y < 2; ++y)
{
dp[x][y][i][now] = INF;
for(int z = 0; z < 2; ++z)
dp[x][y][i][now] = min(dp[x][y][i][now], dp[x][z][i - 1][now] + dp[z][y][i - 1][fa[i - 1][now]]);
}
for(int i = head[now], v; i != -1; i = e[i].nxt)
if((v = e[i].to) ^ _f) dfs3(v, now);
}
In ll solve(int x, bool a, int y, bool b)
{
if(dep[x] < dep[y]) swap(x, y), swap(a, b);
ll rx[2] = {INF, INF}, ry[2] = {INF, INF};
ll nx[2], ny[2];
rx[a] = f[x][a], ry[b] = f[y][b];
for(int i = N; i >= 0; --i)
if(dep[x] - (1 << i) >= dep[y])
{
nx[0] = nx[1] = INF;
for(int j = 0; j < 2; ++j)
for(int k = 0; k < 2; ++k)
nx[j] = min(nx[j], rx[k] + dp[k][j][i][x]);
rx[0] = nx[0], rx[1] = nx[1], x = fa[i][x];
}
if(x == y) return rx[b] + g[x][b];
for(int i = N; i >= 0; --i)
if(fa[i][x] ^ fa[i][y])
{
nx[0] = nx[1] = ny[0] = ny[1] = INF;
for(int j = 0; j < 2; ++j)
for(int k = 0; k < 2; ++k)
{
nx[j] = min(nx[j], rx[k] + dp[k][j][i][x]);
ny[j] = min(ny[j], ry[k] + dp[k][j][i][y]);
}
rx[0] = nx[0], rx[1] = nx[1], x = fa[i][x];
ry[0] = ny[0], ry[1] = ny[1], y = fa[i][y];
}
int tp = fa[0][x];
ll ret0 = f[tp][0] - f[x][1] - f[y][1] + rx[1] + ry[1] + g[tp][0];
ll ret1 = f[tp][1] - min(f[x][0], f[x][1]) - min(f[y][0], f[y][1]) + min(rx[0], rx[1]) + min(ry[0], ry[1]) + g[tp][1];
return min(ret0, ret1);
}
int main()
{
Mem(head, -1);
n = read(); m = read(); char ch[2]; scanf("%s", ch);
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i < n; ++i)
{
int x = read(), y = read();
addEdge(x, y), addEdge(y, x);
if(x > y) swap(x, y);
s.insert(mp(x, y));
}
dfs1(1, 0); dfs2(1, 0); dfs3(1, 0);
for(int i = 1; i <= m; ++i)
{
int x = read(), a = read(), y = read(), b = read();
if(x > y) swap(x, y), swap(a, b);
if(!a && !b && s.find(mp(x, y)) != s.end()) puts("-1");
else write(solve(x, a, y, b)), enter;
}
return 0;
}