【倍增DP】——保卫王国

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 inline ll read(){
  5     ll xx=0,ff=1;
  6     char c=getchar();
  7     while(!isdigit(c)){
  8         if(c=='-') ff=-1;
  9         c=getchar();
 10     }
 11     while(isdigit(c)){
 12         xx=(xx<<1)+(xx<<3)+(c^48);
 13         c=getchar();
 14     }
 15     return xx*ff;
 16 }
 17 const ll N=1e5+10;
 18 const ll inf=1e15;
 19 ll n,m,cnt=0;
 20 ll head[N<<1];
 21 ll p[N];
 22 char c[5];
 23 ll f[N][2];
 24 ll g[N][2];
 25 ll h[N][30][2][2];
 26 ll lc[N][30];
 27 ll dep[N];
 28 ll fad[N];
 29 set<pair<int,int> > sea;
 30 struct edge{
 31     ll to,next;
 32 }e[N<<1];
 33 void addedge(ll from,ll to){e[++cnt]=(edge){to,head[from]};head[from]=cnt;}
 34 void dfs(int u,int fa){
 35     dep[u]=dep[fa]+1;
 36     lc[u][0]=fa;
 37     f[u][1]=p[u];
 38     for(int i=head[u];i;i=e[i].next){
 39         int v=e[i].to;
 40         if(v==fa) continue;
 41         dfs(v,u);
 42         f[u][0]+=f[v][1];
 43         f[u][1]+=min(f[v][0],f[v][1]);
 44     }
 45 }
 46 void dfs2(int u){
 47     for(int i=head[u];i;i=e[i].next){
 48         int v=e[i].to;
 49         if(v==lc[u][0]) continue;
 50         g[v][0]=g[u][1]+f[u][1]-min(f[v][0],f[v][1]); 
 51         g[v][1]=min(g[v][0],f[u][0]+g[u][0]-f[v][1]);
 52         dfs2(v);
 53     }
 54 }
 55 
 56 ll solve(ll x,ll x_s,ll y,ll y_s){
 57     if(dep[x]<=dep[y]) swap(x,y),swap(x_s,y_s);
 58     ll chx[2]={inf,inf},chy[2]={inf,inf};
 59     chx[x_s]=f[x][x_s];
 60     chy[y_s]=f[y][y_s];
 61     ll nowx[2],nowy[2];
 62     for(int j=20;j>=0;j--){
 63         if(dep[lc[x][j]]>=dep[y]){
 64             nowx[0]=nowx[1]=inf;
 65             for(int a=0;a<2;a++){
 66                 for(int b=0;b<2;b++){
 67                     nowx[a]=min(nowx[a],h[x][j][b][a]+chx[b]);
 68                 }
 69             }
 70             chx[0]=nowx[0];chx[1]=nowx[1];
 71             x=lc[x][j];
 72         }
 73     }
 74     if(x==y) return chx[y_s]+g[x][y_s];
 75     for(int j=20;j>=0;j--){
 76         if(lc[x][j]!=lc[y][j]){
 77             nowx[0]=nowx[1]=nowy[0]=nowy[1]=inf;
 78             for(int a=0;a<2;a++){
 79                 for(int b=0;b<2;b++){
 80                     nowx[a]=min(nowx[a],chx[b]+h[x][j][b][a]);
 81                     nowy[a]=min(nowy[a],chy[b]+h[y][j][b][a]);
 82                 }
 83             }
 84             chx[0]=nowx[0],chx[1]=nowx[1],chy[0]=nowy[0],chy[1]=nowy[1];
 85             x=lc[x][j],y=lc[y][j];
 86         }
 87     }
 88     int top=lc[x][0];
 89     ll ischose[2];
 90     ischose[1]=f[top][1]-min(f[x][0],f[x][1])-min(f[y][0],f[y][1])+min(chx[0],chx[1])+min(chy[0],chy[1])+g[top][1];
 91     ischose[0]=f[top][0]-f[x][1]-f[y][1]+chx[1]+chy[1]+g[top][0];
 92     return min(ischose[1],ischose[0]);
 93 }
 94 int main(){
 95     n=read();m=read();
 96     cin>>c;
 97     for(int i=1;i<=n;i++){
 98         p[i]=read();
 99     } 
100     for(int i=1,x,y;i<n;i++){
101         x=read();y=read();
102         addedge(x,y);
103         addedge(y,x);
104         sea.insert(make_pair(x,y));
105         sea.insert(make_pair(y,x));
106     }
107     dfs(1,0);
108     dfs2(1);
109     for(int i=1;i<=n;i++){
110         h[i][0][1][1]=f[lc[i][0]][1]-min(f[i][0],f[i][1]);
111         h[i][0][0][1]=f[lc[i][0]][1]-min(f[i][0],f[i][1]);
112         h[i][0][1][0]=f[lc[i][0]][0]-f[i][1];
113         h[i][0][0][0]=inf;
114     }
115     for(int j=1;j<=19;j++){
116         for(int i=1;i<=n;i++){
117             int tmp=lc[i][j-1];
118             lc[i][j]=lc[tmp][j-1];
119             for(int a=0;a<2;a++){
120                 for(int b=0;b<2;b++){
121                     h[i][j][a][b]=inf;
122                     for(int d=0;d<2;d++){
123                         h[i][j][a][b]=min(h[i][j][a][b],h[i][j-1][a][d]+h[tmp][j-1][d][b]);
124                     }
125                 }
126             }
127         }
128     }
129 
130     for(int i=1,x,y,a,b;i<=m;i++){
131         x=read();a=read();y=read();b=read();
132         if(!a&&!b&&sea.find(make_pair(x,y))!=sea.end()){
133             printf("-1\n");
134             continue;
135         }
136         printf("%lld\n",solve(x,a,y,b));
137     }
138     return 0;
139 }