P5024 [noip2018 improvement group] solution to defending the Kingdom

Ideas :

We can use tree $DP$ Find a point in linear time $u$ If the color is $c$ , Then the minimum cost of the whole tree is $f_{u,c}$

( The specific method is to form a tree from bottom to top $DP$ Draw point $u$ If elected $c$ The minimum cost of this color in the whole subtree is $dp{1}_{u,c}$ , Then from top to bottom $DP$ Draw point $u$ If your father chooses $c$ If this color , With $u$ Root $u$ The minimum cost in the father's tree is $dp{2}_{u,c}$ , The specific details are not detailed here )

It is found that if two points are fixed $u,v$ The colors of are $c,d$ , Then it should be for the tree $u$ To $v$ On the path （ It doesn't contain $u$ and $v$ ） Consider whether to dye black at each point of .

because $dp$ Information is reducible , So if the dyeing scheme on that chain has been determined , We can easily calculate the total cost ： Consider three consecutive points on the path from top to bottom $u,v,w$ The color is $c$ , that $v$ My contribution is $f_{v,c}-dp{1}_{w,d}-dp{2}_{v,d}$ , among $d$ It means that you can and $c$ Adjacent colors . We count this contribution in $(u,v)$ On this side .

Consider how to determine the optimal on chain coloring scheme . For the two chains from top to bottom on the tree , The father at the top of one chain is the bottom of the other chain , We want to merge the information of these two chains . Find out $DP$ The transfer is only related to the color of both ends of the chain , So for a chain, just record whether its two sides are dyed black . Enumerate the colors of two adjacent points when merging , If not all for 0 Then it's legal .

therefore , Let's consider doubling . Make $g_{i,j,k}$ Express $i$ The upward length of the point is $2^j$ Chain , The order is from bottom to top or from top to bottom $DP$ value . In this way, we can transfer through multiplication , Inquiry is like inquiry $LCA$ Same query . Time complexity $O((n+q)logn)$ .

There are many details in the code implementation , Pay attention to the situation of a point in another sub tree when asking for special judgment .

AC code:

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long llong;
const int maxn = 1e5, maxm = 2e5, logn = 16; const llong infl = 1e18 + 1e9 + 1;
int n, m, a[maxn + 3], tot, ter[maxm + 3], nxt[maxm + 3], lnk[maxn + 3];
int dep[maxn + 3], cnt, l[maxn + 3], r[maxn + 3], fa[maxn + 3][logn + 3];
llong dp1[maxn + 3][2], dp2[maxn + 3][2], f[maxn + 3][2];

inline void upd_min(llong &a, llong b) {
    
    a = min(a, b);
}

struct node {
    
    llong dp[2][2];
    node() {
     dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = infl; }
    llong get_min() {
    
        llong ans = infl;
        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
    
            upd_min(ans, dp[i][j]);
        }
        return ans;
    }
    friend inline node merge(const node &a, const node &b) {
    
        node c;
        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
    
            for (int k = 0; k < 2; k++) for (int l = 0; l < 2; l++) {
    
                if (k || l) upd_min(c.dp[i][j], a.dp[i][k] + b.dp[l][j]);
            }
        }
        return c;
    }
} g[maxn + 3][logn + 3][2];

void add_edge(int u, int v) {
    
    ter[++tot] = v;
    nxt[tot] = lnk[u];
    lnk[u] = tot;
}

void dfs1(int u, int p) {
    
    dp1[u][1] = a[u];
    for (int e = lnk[u], v; e; e = nxt[e]) {
    
        if ((v = ter[e]) == p) continue;
        dfs1(v, u);
        dp1[u][0] += dp1[v][1];
        dp1[u][1] += min(dp1[v][0], dp1[v][1]);
    }
}

void dfs2(int u, int p) {
    
    for (int e = lnk[u], v; e; e = nxt[e]) {
    
        if ((v = ter[e]) == p) continue;
        dp2[v][0] = dp2[u][1] + dp1[u][0] - dp1[v][1];
        dp2[v][1] = min(dp2[u][0], dp2[u][1]) + dp1[u][1] - min(dp1[v][0], dp1[v][1]);
        dfs2(v, u);
    }
    f[u][0] = dp2[u][1];
    f[u][1] = a[u] + min(dp2[u][0], dp2[u][1]);
    for (int e = lnk[u], v; e; e = nxt[e]) {
    
        if ((v = ter[e]) == p) continue;
        f[u][0] += dp1[v][1];
        f[u][1] += min(dp1[v][0], dp1[v][1]);
    }
}

void dfs3(int u, int p) {
    
    dep[u] = dep[p] + 1, fa[u][0] = p;
    l[u] = r[u] = ++cnt;
    llong A = f[p][0] - dp1[u][1] - dp2[p][1];
    llong B = f[p][1] - min(dp1[u][0], dp1[u][1]) - min(dp2[p][0], dp2[p][1]);
    g[u][0][0].dp[0][0] = A, g[u][0][0].dp[1][1] = B;
    g[u][0][1].dp[0][0] = A, g[u][0][1].dp[1][1] = B;
    for (int i = 0, t; (t = fa[fa[u][i]][i]); i++) {
    
        fa[u][i + 1] = t;
        g[u][i + 1][0] = merge(g[u][i][0], g[fa[u][i]][i][0]);
        g[u][i + 1][1] = merge(g[fa[u][i]][i][1], g[u][i][1]);
    }
    for (int e = lnk[u], v; e; e = nxt[e]) {
    
        if ((v = ter[e]) == p) continue;
        dfs3(v, u), r[u] = r[v];
    }
}

llong solve(int u, int a, int v, int b) {
    
    if (dep[u] > dep[v]) swap(u, v), swap(a, b);
    node A, B;
    B.dp[b][b] = f[v][b] - (!b ? dp2[v][1] : min(dp2[v][0], dp2[v][1]));
    if (l[u] <= l[v] && l[v] <= r[u]) {
    
        int diff = dep[v] - dep[u] - 1;
        for (int i = 0; i <= logn; i++) {
    
            if (diff >> i & 1) {
    
                B = merge(g[v][i][1], B);
                v = fa[v][i];
            }
        }
        A.dp[a][a] = f[u][a] - (!a ? dp1[v][1] : min(dp1[v][0], dp1[v][1]));
        return merge(A, B).get_min();
    }
    A.dp[a][a] = f[u][a] - (!a ? dp2[u][1] : min(dp2[u][0], dp2[u][1]));
    int diff = dep[v] - dep[u];
    for (int i = 0; i <= logn; i++) {
    
        if (diff >> i & 1) {
    
            B = merge(g[v][i][1], B);
            v = fa[v][i];
        }
    }
    if (fa[u][0] == fa[v][0]) goto next_part;
    for (int i = logn; ~i; i--) {
    
        if (fa[u][i] != fa[v][i]) {
    
            A = merge(A, g[u][i][0]);
            B = merge(g[v][i][1], B);
            u = fa[u][i], v = fa[v][i];
        }
    }
    next_part:;
    node C; int x = fa[u][0];
    C.dp[0][0] = f[x][0] - dp1[u][1] - dp1[v][1];
    C.dp[1][1] = f[x][1] - min(dp1[u][0], dp1[u][1]) - min(dp1[v][0], dp1[v][1]);
    return merge(A, merge(C, B)).get_min();
}

int main() {
    
    scanf("%d %d %*s", &n, &m);
    for (int i = 1; i <= n; i++) {
    
        scanf("%d", &a[i]);
    }
    for (int i = 1, u, v; i < n; i++) {
    
        scanf("%d %d", &u, &v);
        add_edge(u, v), add_edge(v, u);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    /* for (int i = 1; i <= n; i++) { for (int j = 0; j < 2; j++) { printf("%d %d %lld\n", i, j, f[i][j]); } } */
    dfs3(1, 0);
    for (int a, x, b, y; m--; ) {
    
        scanf("%d %d %d %d", &a, &x, &b, &y);
        llong ret = solve(a, x, b, y);
        printf("%lld\n", ret == infl ? -1 : ret);
    }
    return 0;
}