题解 - Vijos

2

November (CLH_W) LV 10 @ 2022-04-06 21:23:27

#include<cstdio>
#include<set>
#include<cctype>
#include<algorithm>
#define maxn 100010
#define maxm 200010
#define ll long long
#define mp make_pair
#define pii pair<int,int>
using namespace std;

int hd[maxn],nxt[maxm],pnt[maxm],tot=0;
int fa[maxn][20],val[maxn],dep[maxn],n,q;
ll f[maxn][2],g[maxn][2],fh[maxn][20][2][2];
const ll INF=1LL<<60;
char Type[10];
set<pii> st;
void read(int &x){
    char ch=x=0;
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
        x=x*10+ch-'0',ch=getchar();
}
void add(int x,int y){
    pnt[++tot]=y,nxt[tot]=hd[x],hd[x]=tot;
}
void dfs(int x,int FA,int d){
    fa[x][0]=FA,dep[x]=d;
    f[x][1]=val[x];
    for(int i=hd[x];i;i=nxt[i]){
        int v=pnt[i];
        if(v==FA)
            continue;
        dfs(v,x,d+1);
        f[x][0]+=f[v][1],f[x][1]+=min(f[v][0],f[v][1]);
    }
}
void dfs_2(int x){
    for(int i=hd[x];i;i=nxt[i]){
        int v=pnt[i];
        if(v==fa[x][0])
            continue;
        g[v][0]=g[x][1]+f[x][1]-min(f[v][0],f[v][1]);
        g[v][1]=min(g[x][0]+f[x][0]-f[v][1],g[v][0]);
        dfs_2(v);
    }
}
ll solve(int x,int a,int y,int b){// x 和 a 互换 , y 和 b 互换
    if(dep[x]<dep[y])
        swap(x,y),swap(a,b);
    ll tx[2]={INF,INF},ty[2]={INF,INF};
    ll nx[2],ny[2];
    tx[a]=f[x][a],ty[b]=f[y][b];
    for(int i=19;~i;i--){
        if(dep[fa[x][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],tx[k]+fh[x][i][k][j]);
            }
            tx[0]=nx[0],tx[1]=nx[1],x=fa[x][i];
        }
    }
    if(x==y)
        return tx[b]+g[x][b];
    for(int i=19;~i;i--){
        if(fa[x][i]!=fa[y][i]){
            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],tx[k]+fh[x][i][k][j]);
                    ny[j]=min(ny[j],ty[k]+fh[y][i][k][j]);
                }
            }
            tx[0]=nx[0],tx[1]=nx[1],x=fa[x][i];
            ty[0]=ny[0],ty[1]=ny[1],y=fa[y][i];
        }
    }
    int lca=fa[x][0];
    ll ans0=f[lca][0]-f[x][1]-f[y][1]+tx[1]+ty[1]+g[lca][0];
    ll ans1=f[lca][1]-min(f[x][0],f[x][1])-min(f[y][0],f[y][1])+min(tx[0],tx[1])+min(ty[0],ty[1])+g[lca][1];
    return min(ans0,ans1);
}
int main(){
    read(n),read(q),scanf("%s",Type);
    for(int i=1;i<=n;i++)
        read(val[i]);
    for(int i=1,u,v;i<=n-1;i++){
        read(u),read(v);
        add(u,v),add(v,u);
        st.insert(mp(u,v)),st.insert(mp(v,u));
    }
    dfs(1,0,1),dfs_2(1);
    for(int i=1;i<=n;i++){
        fh[i][0][0][0]=INF;
        fh[i][0][0][1]=f[fa[i][0]][1]-min(f[i][0],f[i][1]);
        fh[i][0][1][0]=f[fa[i][0]][0]-f[i][1];
        fh[i][0][1][1]=f[fa[i][0]][1]-min(f[i][0],f[i][1]);
    }
    for(int j=1;j<=19;j++){
        for(int i=1;i<=n;i++){
            int tmp=fa[i][j-1];
            fa[i][j]=fa[tmp][j-1];
            for(int u=0;u<2;u++){
                for(int v=0;v<2;v++){
                    fh[i][j][u][v]=INF;
                    for(int w=0;w<2;w++)
                        fh[i][j][u][v]=min(fh[i][j][u][v],fh[i][j-1][u][w]+fh[tmp][j-1][w][v]);
                }
            }
        }
    }
    for(int i=1,a,b,x,y;i<=q;i++){
        read(a),read(x),read(b),read(y);
        if(!x&&!y&&st.find(mp(a,b))!=st.end()){
            puts("-1");
            continue;
        }
        printf("%lld\n",solve(a,x,b,y));
    }
    return 0;
}

0

神-董 (董由) LV 7 @ 2022-07-16 22:31:36

\(\rule{10000000mm}{100000000mm}\)

0

孙鹤鸣 (sunheming) LV 10 @ 2020-03-24 13:45:40

考场上一眼动态dp。。然而又看到没有修改点权，所以倍增就好了

令 T 为整棵树，设 f[i][0/1]表示（以 i 为根的子树），其中 i 选/不选的最小代价，g[i][0/1] 为（ T- 以 i为根的子树），其中 i 选/不选的最小代价。这两个数组可以树形dp求出。

然后令 anc 表示 i 的 2^j
j
祖先， fh[i][j][0/1][0/1]表示（anc的子树 - \ i 的子树），其中 i的状态为 0/10/1 ，ancanc 的状态为 0/10/1 的最小代价，这个数组可以枚举 ii 的 2^{j-1}2
j−1
祖先的状态直接转移。

然后有了这些数组我们就可以处理询问了。

如果 a 是 b 的祖先，那么可以直接倍增上去（还是像 fh 一样合并倍增数组，枚举中间点的状态即可），然后不要忘了加上 g[a][x]。
否则我们需要先把 a 和 b都倍增到 lca的儿子处，然后枚举 lca 和两个儿子的状态，具体可以见代码。
复杂度 O((n+q) \log n) ，不是最优算法，但已经可以通过本题。

附考场代码，赶时间写的，所以不美观。。
```cpp
#include<cstdio>
#include<set>
#include<cctype>
#include<algorithm>
#define maxn 100010
#define maxm 200010
#define ll long long
#define mp make_pair
#define pii pair<int,int>
using namespace std;

int hd[maxn],nxt[maxm],pnt[maxm],tot=0;
int fa[maxn][20],val[maxn],dep[maxn],n,q;
ll f[maxn][2],g[maxn][2],fh[maxn][20][2][2];
const ll INF=1LL<<60;
char Type[10];
set<pii> st;
void read(int &x){
char ch=x=0;
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
x=x*10+ch-'0',ch=getchar();
}
void add(int x,int y){
pnt[++tot]=y,nxt[tot]=hd[x],hd[x]=tot;
}
void dfs(int x,int FA,int d){
fa[x][0]=FA,dep[x]=d;
f[x][1]=val[x];
for(int i=hd[x];i;i=nxt[i]){
int v=pnt[i];
if(v==FA)
continue;
dfs(v,x,d+1);
f[x][0]+=f[v][1],f[x][1]+=min(f[v][0],f[v][1]);
}
}
void dfs_2(int x){
for(int i=hd[x];i;i=nxt[i]){
int v=pnt[i];
if(v==fa[x][0])
continue;
g[v][0]=g[x][1]+f[x][1]-min(f[v][0],f[v][1]);
g[v][1]=min(g[x][0]+f[x][0]-f[v][1],g[v][0]);
dfs_2(v);
}
}
ll solve(int x,int a,int y,int b){// x 和 a 互换 , y 和 b 互换
if(dep[x]<dep[y])
swap(x,y),swap(a,b);
ll tx[2]={INF,INF},ty[2]={INF,INF};
ll nx[2],ny[2];
tx[a]=f[x][a],ty[b]=f[y][b];
for(int i=19;~i;i--){
if(dep[fa[x][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],tx[k]+fh[x][i][k][j]);
}
tx[0]=nx[0],tx[1]=nx[1],x=fa[x][i];
}
}
if(x==y)
return tx[b]+g[x][b];
for(int i=19;~i;i--){
if(fa[x][i]!=fa[y][i]){
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],tx[k]+fh[x][i][k][j]);
ny[j]=min(ny[j],ty[k]+fh[y][i][k][j]);
}
}
tx[0]=nx[0],tx[1]=nx[1],x=fa[x][i];
ty[0]=ny[0],ty[1]=ny[1],y=fa[y][i];
}
}
int lca=fa[x][0];
ll ans0=f[lca][0]-f[x][1]-f[y][1]+tx[1]+ty[1]+g[lca][0];
ll ans1=f[lca][1]-min(f[x][0],f[x][1])-min(f[y][0],f[y][1])+min(tx[0],tx[1])+min(ty[0],ty[1])+g[lca][1];
return min(ans0,ans1);
}
int main(){
read(n),read(q),scanf("%s",Type);
for(int i=1;i<=n;i++)
read(val[i]);
for(int i=1,u,v;i<=n-1;i++){
read(u),read(v);
add(u,v),add(v,u);
st.insert(mp(u,v)),st.insert(mp(v,u));
}
dfs(1,0,1),dfs_2(1);
for(int i=1;i<=n;i++){
fh[i][0][0][0]=INF;
fh[i][0][0][1]=f[fa[i][0]][1]-min(f[i][0],f[i][1]);
fh[i][0][1][0]=f[fa[i][0]][0]-f[i][1];
fh[i][0][1][1]=f[fa[i][0]][1]-min(f[i][0],f[i][1]);
}
for(int j=1;j<=19;j++){
for(int i=1;i<=n;i++){
int tmp=fa[i][j-1];
fa[i][j]=fa[tmp][j-1];
for(int u=0;u<2;u++){
for(int v=0;v<2;v++){
fh[i][j][u][v]=INF;
for(int w=0;w<2;w++)
fh[i][j][u][v]=min(fh[i][j][u][v],fh[i][j-1][u][w]+fh[tmp][j-1][w][v]);
}
}
}
}
for(int i=1,a,b,x,y;i<=q;i++){
read(a),read(x),read(b),read(y);
if(!x&&!y&&st.find(mp(a,b))!=st.end()){
puts("-1");
continue;
}
printf("%lld\n",solve(a,x,b,y));
}
return 0;
}
```

题解

3 条题解

保卫王国

信息

状态

开发

支持

题解

3 条题解

保卫王国

信息

状态

开发

支持

还没有账户？

登录