LOJ#2955 保卫王国 题解

1
// int h[N][17][2][2]
2
auto H=h[y][0];
3
H[1][0]=f[x][0]-f[y][1];
4
H[1][1]=H[0][1]=f[x][1]-min(f[y][0],f[y][1]);
5
// 然后倍增一下

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
    int a=0, f=1; char c=getchar();
17
    while(!isdigit(c)) {
18
        if(c=='-') f=-1;
19
        c=getchar();
20
    }
21
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
    return a*f;
23
}
24
const int N=1e5+5, inf=0x0f0f0f0f0f0f0f0f;
25
int n, m, lim, c[N], dep[N];
26
int f[N][2], g[N][2];
27
int fa[N][17], h[N][17][2][2];
28
vector<int> p[N];
29
char s[5];
30
void dfs1(int x,int fr)
31
{
32
    dep[x]=dep[fr]+1;
33
    fa[x][0]=fr;
34
    for(int i=1;(1<<i)<=dep[x];++i) fa[x][i]=fa[fa[x][i-1]][i-1];
35
    f[x][0]=0, f[x][1]=c[x];
36
    for(auto y:p[x]) if(y!=fr) {
37
        dfs1(y,x);
38
        f[x][0]+=f[y][1];
39
        f[x][1]+=min(f[y][0],f[y][1]);
40
    }
41
}
42
void dfs2(int x,int fr) {
43
    for(auto y:p[x]) if(y!=fr) {
44

45
        g[y][0]=g[x][1]+f[x][1]-min(f[y][0],f[y][1]);
46
        g[y][1]=min(g[x][0]+f[x][0]-f[y][1],g[y][0]);
47

48
        auto H=h[y][0];
49
        H[1][0]=f[x][0]-f[y][1];
50
        H[1][1]=H[0][1]=f[x][1]-min(f[y][0],f[y][1]);
51
        for(int i=1;(1<<i)<=dep[y];++i) rep(a,0,1) rep(b,0,1) rep(c,0,1) {
52
            h[y][i][a][c]=min(h[y][i][a][c],h[y][i-1][a][b]+h[fa[y][i-1]][i-1][b][c]);
53
        }
54
        dfs2(y,x);
55
    }
56
}
57
vector<int> calc(int x,int a,int y) {
58
    vector<int> res(2);
59
    res[a]=0;
60
    res[a^1]=inf;
61
    for(int i=lim;~i;--i) if(fa[x][i]&&dep[fa[x][i]]>=dep[y]) {
62
        vector<int> t(2,inf);
63
        rep(a,0,1) rep(b,0,1) t[b]=min(t[b],res[a]+h[x][i][a][b]);
64
        x=fa[x][i], res=t;
65
    }
66
    return res;
67
}
68
int solve(int x,int a,int y,int b) {
69

70
    int tx=x, ty=y;
71
    for(int i=lim;~i;--i) if(fa[x][i]&&dep[fa[x][i]]>=dep[y]) x=fa[x][i];
72
    if(x==y) {
73
        return calc(tx,a,y)[b]+f[tx][a]+g[y][b];
74
    }
75
    for(int i=lim;~i;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i], y=fa[y][i];
76
    int z=fa[x][0];
77
    auto F=calc(tx,a,x), G=calc(ty,b,y);
78
    int res0=F[1]+G[1]+(f[z][0]-f[x][1]-f[y][1])+g[z][0];
79
    int res1=min(F[0],F[1])+min(G[0],G[1])+(f[z][1]-min(f[x][0],f[x][1])-min(f[y][0],f[y][1]))+g[z][1];
80
    // 两种情况为z是否驻军
81
    return min(res0,res1)+f[tx][a]+f[ty][b];
82
}
83
signed main() {
84
    freopen("defense.in","r",stdin);
85
    freopen("defense.out","w",stdout);
86
    n=read(), m=read();
87
    scanf("%s",s);
88
    rep(i,1,n) c[i]=read();
89
    rep(i,2,n) {
90
        int x=read(), y=read();
91
        p[x].pb(y), p[y].pb(x);
92
    }
93
    while(1<<(lim+1)<=n) ++lim;
94
    SET(h,0x0f);
95
    dfs1(1,0);
96
    dfs2(1,0);
97
    while(m--) {
98
        int x=read(), a=read(), y=read(), b=read();
99
        if(dep[x]<dep[y]) swap(x,y), swap(a,b);
100
        if(!a&&!b&&fa[x][0]==y) puts("-1");
101
        else printf("%lld\n",solve(x,a,y,b));
102
    }
103
    return 0;
104
}