Luogu | P5024 [NOIp 2018] 保卫王国 | 动态规划 | 动态动态规划 / 倍增


Description

Z 国有 $n$ 座城市,$n – 1$ 条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。

Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件:

  • 一座城市可以驻扎一支军队,也可以不驻扎军队。
  • 由道路直接连接的两座城市中至少要有一座城市驻扎军队。
  • 在城市里驻扎军队会产生花费,在编号为 $i$ 的城市中驻扎军队的花费是 $p_i$。

小 Z 很快就规划出了一种驻扎军队的方案,使总花费最小。但是国王又给小 Z 提出了 $m$ 个要求,每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一 给出回答。具体而言,如果国王提出的第 $j$ 个要求能够满足上述驻扎条件(不需要考虑第 $j$ 个要求之外的其它要求),则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第 $j$ 个要求无法满足,则需要输出 $-1$。现在请你来帮助小 Z。


Input Format

第 $1$ 行包含两个正整数 $n,m$ 和一个字符串 type,分别表示城市数、要求数和数据类型。$type$ 是一个由大写字母 $A$,$B$ 或 $C$ 和一个数字 $1$,$2$,$3$ 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中有具体的描述。

第 $2$ 行 $n$ 个整数 $p_i$,表示编号 $i$ 的城市中驻扎军队的花费。

接下来 $n – 1$ 行,每行两个正整数 $<u,v>$,表示有一条 $u$ 到 $v$ 的双向道路。

接下来 $m$ 行,第 $j$ 行四个整数 $a,x,b,y(a ≠ b)$,表示第 $j$ 个要求是在城市 $a$ 驻扎 $x$ 支军队, 在城市 $b$ 驻扎 $y$ 支军队。其中,$x$ 、 $y$ 的取值只有 $0$ 或 $1$:若 $x$ 为 $0$,表示城市 $a$ 不得驻 扎军队,若 $x$ 为 $1$,表示城市 $a$ 必须驻扎军队;若 $y$ 为 $0$,表示城市 $b$ 不得驻扎军队, 若 $y$ 为 $1$,表示城市 $b$ 必须驻扎军队。

输入文件中每一行相邻的两个数据之间均用一个空格分隔。


Output Format

输出共 $m$ 行,每行包含 $1$ 个整数,第 $j$ 行表示在满足国王第 $j$ 个要求时的最小开销, 如果无法满足国王的第$j$ 个要求,则该行输出 $-1$。


Input Sample

Sample 01

5 3 C3
2 4 1 3 9
1 5
5 2
5 3
3 4
1 0 3 0
2 1 3 1
1 0 5 0


Output Sample

Sample 01

12
7
-1


Data Range

$n,m,p_i \le 10^5$。


Solution

由于询问之间互不影响,故每次询问 $<u,x,v,y>$ 受到影响的 dp 区间在 $[u,lca],[v,lca],[lca,1]$ 内。考虑预处理出所有的情况。

设 $f[i][0/1]$ 为以点 $i$ 为根的子树,其中 $i$ 点不选 / 选的最小权值。

设 $g[i][0/1]$ 为总树减去以点 $i$ 为根的子树,其中 $i$ 点 不必选 / 必选的最小权值。

设 $dp[i][j][0/1][0/1]$ 为以点 $i$ 的 $2^j$ 辈的祖先为根的子树,减去以 $i$ 点为根的子树(其中第一个 0/1 表示点 $i$ 不选/ 选,第二个 0/1 表示点 $i$ 选)的最小权值。

则考虑倍增过程中计算答案。设询问 $<u,v>$ 中深度较大者为 $u$。预处理,倍增过程及注意事项详见注释。

此题也有 [NOI+ / CTSC] 的 动态动态规划 做法,不会。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

#define log 16
#define URF 0x3f3f3f3f3f3f3f3f

typedef long long ll;

int buf[20];

template <class T> inline void Read(T &x){
    x=0;
    char ch=0;
    bool neg=0;
    while(ch<'0'||ch>'9')
        ch=getchar(),neg|=(ch=='-');
    while(ch>='0'&&ch<='9')
        x=x*10+ch-48,ch=getchar();
    x*=neg?-1:1;
    return;
}

template <class T> inline void Write(T x){
    if(!x){
        putchar('0');
        putchar('\n');
        return;
    }
    if(x<0){
        x=-x;
        putchar('-');
    }
    int cntr=0;
    while(x)
        buf[++cntr]=x%10,x/=10;
    for(int i=cntr;i;i--)
        putchar(buf[i]+48);
    putchar('\n');
    return;
}

struct edge{
    int from;
    int to;
    int next;
}e[200005];

int N;
int M;
int node;

int pw[20];
int w[100005];
int dep[100005];
int first[100005];
int last[100005];

int fa[100005][20];

ll f[100005][2];
ll g[100005][2];
ll dp[100005][20][2][2];

char str[5];

void addedge(int u,int v){
    e[++node]=(edge){u,v,0};
    if(first[u]==0) first[u]=node;
    else e[last[u]].next=node;
    last[u]=node; return;
}

void pDFS(int x){
    rep(i,1,log) fa[x][i]=fa[fa[x][i-1]][i-1];
    f[x][1]=w[x];
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to;
        if(y==fa[x][0])
            continue;
        fa[y][0]=x;
        dep[y]=dep[x]+1;
        pDFS(y);
        f[x][0]+=f[y][1];
        f[x][1]+=min(f[y][0],f[y][1]);
    }
    return;
}

void pDFS2(int x){
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to;
        if(y==fa[x][0])
            continue;
        g[y][0]=g[x][1]+f[x][1]-min(f[y][0],f[y][1]); // y 不选,则 x 必选,即为 g[x][1] + f[x][1] 减去 y 不必选的贡献(因为 g 不包含 y 这颗子树,所以要将其计算答案过程中产生的贡献减掉) 
        g[y][1]=min(g[y][0],g[x][0]+f[x][0]-f[y][1]); // y 选,则 x 可选可不选,选的情况同 g[y][0],不选的情况即为 g[x][0] + f[x][0] 减去 y 选的贡献 
        pDFS2(y);
    }
    return;
}

ll GetAnswer(int u,int vu,int v,int vv){
    if(dep[u]<dep[v]){
        swap(u,v);
        swap(vu,vv);
    }
    ll A_u[2]; // 当前爬升过程中,以点 u 为根的子树 不选 / 选 的累计答案 
    ll A_v[2]; // 当前爬升过程中,以点 v 为根的子树 不选 / 选 的累计答案 
    ll A_cu[2]; // 当前爬升过程中,以点 u 的当前爬升的祖先为根的子树 不选 / 选 的累计答案 
    ll A_cv[2]; // 当前爬升过程中,以点 v 的当前爬升的祖先为根的子树 不选 / 选 的累计答案 
    A_u[vu]=f[u][vu],A_u[1-vu]=URF; // 设置 u 的初始限制条件 
    A_v[vv]=f[v][vv],A_v[1-vv]=URF; // 设置 v 的初始限制条件 
    int dlt=dep[u]-dep[v];
    rep(i,0,log){ // 将 u 爬升到与 v 同一高度 
        if(dlt&pw[i]){
            A_cu[0]=A_cu[1]=URF;
            A_cu[0]=min(A_u[0]+dp[u][i][0][0],A_u[1]+dp[u][i][1][0]); // u 的祖先不选,枚举 u 选或不选,向上爬升,计算 u 的祖先的答案 
            A_cu[1]=min(A_u[0]+dp[u][i][0][1],A_u[1]+dp[u][i][1][1]); // u 的祖先选,枚举 u 选或不选,向上爬升,计算 u 的祖先的答案 
            A_u[0]=A_cu[0],A_u[1]=A_cu[1],u=fa[u][i]; // u 爬升到其祖先,更新答案 
        }
    }
    if(u==v)
        return A_u[vv]+g[u][vv]; // LCA 为 v,此时因为 v 没有倍增,故限制条件无法限制 v,则在此处限制 
    for(int i=log;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){ // 倍增过程同上 
            A_cu[0]=A_cu[1]=URF;
            A_cv[0]=A_cv[1]=URF;
            A_cu[0]=min(A_u[0]+dp[u][i][0][0],A_u[1]+dp[u][i][1][0]);
            A_cu[1]=min(A_u[0]+dp[u][i][0][1],A_u[1]+dp[u][i][1][1]);
            A_cv[0]=min(A_v[0]+dp[v][i][0][0],A_v[1]+dp[v][i][1][0]);
            A_cv[1]=min(A_v[0]+dp[v][i][0][1],A_v[1]+dp[v][i][1][1]);
            u=fa[u][i],v=fa[v][i];
            A_u[0]=A_cu[0],A_u[1]=A_cu[1];
            A_v[0]=A_cv[0],A_v[1]=A_cv[1];
        }
    }
    int lca=fa[v][0]; // LCA 不是 u 或 v,则 LCA 没有限制条件 
    ll lca0=f[lca][0]-f[v][1]-f[u][1]+A_u[1]+A_v[1]+g[lca][0]; // LCA 不选,则两颗子树必选 
    ll lca1=f[lca][1]-min(f[u][0],f[u][1])-min(f[v][0],f[v][1])+min(A_u[0],A_u[1])+min(A_v[0],A_v[1])+g[lca][1]; // LCA 选,则两颗子树不是必选,取最小值 
    return min(lca0,lca1);
}

int main(){
    int u,vu,v,vv;
    Read(N);
    Read(M);
    scanf("%s",str+1);
    rep(i,1,N)
        Read(w[i]);
    rep(i,2,N){
        Read(u);
        Read(v);
        addedge(u,v);
        addedge(v,u);
    }
    pDFS(1);
    pDFS2(1);
    rep(i,0,20)
        pw[i]=1<<i;
    wipe(dp,URF); // 此处数组必须全部置 inf 
    rep(i,1,N){
        // dp[i][0][0][0] 不合法,不管 
        dp[i][0][1][0]=f[fa[i][0]][0]-f[i][1]; // i 选,fa[i] 不选,减去 i 对于 f[i][0] 做的贡献 
        dp[i][0][0][1]=f[fa[i][0]][1]-min(f[i][0],f[i][1]); // i 不选,fa[i] 选,由于此处不包含 y 所在的子树,所以减去 i 对于 f[i][1] 做的贡献 
        dp[i][0][1][1]=f[fa[i][0]][1]-min(f[i][0],f[i][1]); // 同上,由于不包含 y 所在的子树,所以直接减去贡献 
    }
    rep(i,1,log){
        rep(j,1,N){
            dp[j][i][0][0]=min(dp[j][i][0][0],min(dp[j][i-1][0][0]+dp[fa[j][i-1]][i-1][0][0],dp[j][i-1][0][1]+dp[fa[j][i-1]][i-1][1][0])); // 枚举中间做跳板的点选 / 不选,下同 
            dp[j][i][0][1]=min(dp[j][i][0][1],min(dp[j][i-1][0][0]+dp[fa[j][i-1]][i-1][0][1],dp[j][i-1][0][1]+dp[fa[j][i-1]][i-1][1][1]));
            dp[j][i][1][0]=min(dp[j][i][1][0],min(dp[j][i-1][1][0]+dp[fa[j][i-1]][i-1][0][0],dp[j][i-1][1][1]+dp[fa[j][i-1]][i-1][1][0]));
            dp[j][i][1][1]=min(dp[j][i][1][1],min(dp[j][i-1][1][0]+dp[fa[j][i-1]][i-1][0][1],dp[j][i-1][1][1]+dp[fa[j][i-1]][i-1][1][1]));
        }
    }
    rep(i,1,M){
        Read(u);
        Read(vu);
        Read(v);
        Read(vv);
        if(!vu && !vv && (fa[v][0]==u || fa[u][0]==v))
            Write(-1);
        else
            Write(GetAnswer(u,vu,v,vv));
    }
    return 0;
}