[BZOJ5466][NOIP2018]保卫王国倍增

首先可以写一个暴力dp的式子，非常经典的树形dp

\(dp[i][0]\)表示\(i\)这个点没有驻军，\(dp[i][1]\)就是有驻军，\(j\)是\(i\)的孩子。那么显然：

\[\begin{align*}
dp[i][0]&=dp[j][1]\\
dp[i][1]&=\min\{dp[j][0],dp[j][1]\}
\end{align*}
\]

然后我们发现，对于一个孩子\(j\)，它的转移与其他孩子无关。也就是其他孩子的值对他没有影响。

这样的性质决定了这道题目的可倍增性。

在说到倍增前，我们再做个预处理，设\(h[i][0/1]\)分别表示无或有驻军的时候，除了\(i\)的子树外的最优值。那么有

\[\begin{align*}
h[j][0]&=h[i][1]+dp[i][1]-\min\{dp[j][0],dp[j][1]\}\\
h[j][1]&=\min\{h[i][0]+dp[i][0]-dp[j][1]\ ,\ h[i][1]+dp[i][1]-\min\{dp[j][0],dp[j][1]\}\}
\end{align*}
\]

下面，我们再回去看一下题目。可以发现，每一次会影响到的点，只在\(x\)到\(y\)的路径上还有在\(lca\)到跟的路径上。

对于其它点，根据我们之前的结论，对\(x\)与\(y\)的操作，与它们无关。所以我们只需要搞定会影响到的点。

我们考虑先把路径外的点得该用的值先做出来。对于树上的路径，倍增是很实用的。

定义\(f[i][j]\)表示\(i\)的第\(2^j\)层祖先，\(p[i][j][0/1][0/1]\)表示\(i\)取不取，那个祖先取不取的不计算上\(i\)的最优解。

初始化：

\[\begin{align*}
f[i][0]&=fa\\
p[i][0][0][0]&=INF\\
p[i][0][1][0]&=dp[fa][0]-dp[i][1]\\
p[i][0][0][1]&=dp[fa][1]-\min\{dp[i][0],dp[i][1]\}\\
p[i][0][1][1]&=dp[fa][1]-\min\{dp[i][0],dp[i][1]\}
\end{align*}
\]

转移的话找相同的中间值转移就可以了。

\[\begin{align*}
f[i][j]&=f[f[i][j-1]][j-1]\\
p[i][j][0][0]&=\min\{p[i][j-1][0][0]+p[f[i][j-1]][j-1][0][0],p[i][j-1][0][1]+p[f[i][j-1]][j-1][1][0]\}\\
p[i][j][0][1]&=\min\{p[i][j-1][0][0]+p[f[i][j-1]][j-1][0][1],p[i][j-1][0][1]+p[f[i][j-1]][j-1][1][1]\}\\
p[i][j][1][0]&=\min\{p[i][j-1][1][0]+p[f[i][j-1]][j-1][0][0],p[i][j-1][1][1]+p[f[i][j-1]][j-1][1][0]\}\\
p[i][j][1][1]&=\min\{p[i][j-1][1][0]+p[f[i][j-1]][j-1][0][1],p[i][j-1][1][1]+p[f[i][j-1]][j-1][1][1]\}
\end{align*}
\]

然后处理询问的时候，设置\(x0,x1,y0,y1\)几个值，存下到目前的\(x,y\)分别选/不选的答案。

如果被禁止了选还是不选，那么就设置对应的值为\(INF\)

也还是找相同的中间值。这里跟这个差不多，就略去转移过程。

为什么这样是对的呢？

我们来看一下一种情况的不可能性。

倍增一条从上到下的链，中间虽然在不考虑最下面那个点的时候通过\(0\)转移，但是考虑上\(i\)以后通过\(1\)转移。

这就给归功于我们限制了最底下的点的选择类型了。只要限制下了最底下的选择类型，那么我们的计入这个点和不计入的话每一个状态的差值都是一样的，也就是说相对大小也是一样的。因此，转移的方式也是不变的。

如果上面不太好理解的话，这里有一个比较抽象的理解方式：

如果给了一条链，告诉你某一个边缘上的点选和不选时候的两个答案，那么我们不管dp的过程，直接想一想，可以直接对应的拼上去，绝对是不会错的。

#include<cstdio>

#include<algorithm>

#include<cstring>

#define REP(i,a,n) for(register int i(a);i<=(n);++i)

#define PER(i,a,n) for(register int i(a);i>=(n);--i)

#define FEC(i,x,y) for(register int i=head[x],y=g[i].to;i;i=g[i].ne,y=g[i].to)

#define dbg(...) fprintf(stderr,__VA_ARGS__)

const int SZ=(1<<21)+1;char ibuf[SZ],*iS,*iT,obuf[SZ+128],*oS=obuf,*oT=obuf+SZ-1;

#ifdef ONLINE_JUDGE

#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SZ,stdin),(iS==iT?EOF:*iS++)):*iS++)

#else

#define gc() getchar()

#endif

template<typename I>inline void read(I&x){char c=gc();int f=0;for(;c<'0'||c>'9';c=gc())c=='-'?f=1:0;for(x=0;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c&15);f?x=-x:0;}

inline void flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}

#define printf(...) (oS>oT&&(flush(),1),oS+=sprintf(oS,__VA_ARGS__))

template<typename A,typename B>inline char SMAX(A&a,const B&b){return a<b?a=b,1:0;}

template<typename A,typename B>inline char SMIN(A&a,const B&b){return a>b?a=b,1:0;}

typedef long long ll;typedef unsigned long long ull;typedef std::pair<int,int>pii;

const int N=100000+7,LOG=18;const ll INF=0x3f3f3f3f3f3f3f3f;

int n,m,x,y,ha,hb,a[N],f[N][LOG],dep[N];ll dp[N][2],h[N][2],p[N][LOG][2][2],abc;//错误笔记：要开ll

struct Edge{int to,ne;}g[N<<1];int head[N],tot;

inline void Addedge(int x,int y){g[++tot].to=y;g[tot].ne=head[x];head[x]=tot;}

inline void DP(int x,int fa=0){

	dp[x][0]=0;dp[x][1]=a[x];f[x][0]=fa;dep[x]=dep[fa]+1;

	FEC(i,x,y)if(y!=fa)DP(y,x),dp[x][0]+=dp[y][1],dp[x][1]+=std::min(dp[y][0],dp[y][1]);

}

inline void DP2(int x,int fa=0){

	FEC(i,x,y)if(y!=fa)h[y][0]=h[x][1]+dp[x][1]-std::min(dp[y][0],dp[y][1]),//错误笔记：还有一个小错误，因为这里用的是刷表转移的，所以下一行中没注意把x,y打混掉了。

					   h[y][1]=std::min(h[x][0]+dp[x][0]-dp[y][1],h[x][1]+dp[x][1]-std::min(dp[y][0],dp[y][1])),DP2(y,x);//错误笔记：把dp打成f 这不是最重要的，最重要的是要先更新数组再递归！！！

}

inline void Preprocess(){

	REP(i,1,n){

		p[i][0][0][0]=INF;

		p[i][0][1][0]=dp[f[i][0]][0]-dp[i][1];

		p[i][0][1][1]=p[i][0][0][1]=dp[f[i][0]][1]-std::min(dp[i][0],dp[i][1]);//错误笔记：i,x不分

	}

	REP(j,1,LOG-1)REP(i,1,n)f[i][j]=f[f[i][j-1]][j-1],

							p[i][j][0][0]=std::min(p[i][j-1][0][0]+p[f[i][j-1]][j-1][0][0],p[i][j-1][0][1]+p[f[i][j-1]][j-1][1][0]),

							p[i][j][0][1]=std::min(p[i][j-1][0][0]+p[f[i][j-1]][j-1][0][1],p[i][j-1][0][1]+p[f[i][j-1]][j-1][1][1]),

							p[i][j][1][0]=std::min(p[i][j-1][1][0]+p[f[i][j-1]][j-1][0][0],p[i][j-1][1][1]+p[f[i][j-1]][j-1][1][0]),

							p[i][j][1][1]=std::min(p[i][j-1][1][0]+p[f[i][j-1]][j-1][0][1],p[i][j-1][1][1]+p[f[i][j-1]][j-1][1][1]);

}

inline ll Solve(int x,int a,int y,int b){

	if(dep[x]<dep[y])std::swap(x,y),std::swap(a,b);

	ll x0=INF,x1=INF,y0=INF,y1=INF,tx0,ty0,tx1,ty1;

	if(!a)x0=dp[x][0];else x1=dp[x][1];

	if(!b)y0=dp[y][0];else y1=dp[y][1];

	PER(i,LOG-1,0)if(dep[f[x][i]]>=dep[y])tx0=std::min(x0+p[x][i][0][0],x1+p[x][i][1][0]),SMIN(tx0,INF),

										  tx1=std::min(x0+p[x][i][0][1],x1+p[x][i][1][1]),SMIN(tx1,INF),

										  x0=tx0,x1=tx1,x=f[x][i];

	if(x==y)return (b?x1:x0)+h[y][b];

	PER(i,LOG-1,0)if(f[x][i]!=f[y][i])tx0=std::min(x0+p[x][i][0][0],x1+p[x][i][1][0]),SMIN(tx0,INF),

									  tx1=std::min(x0+p[x][i][0][1],x1+p[x][i][1][1]),SMIN(tx1,INF),

									  ty0=std::min(y0+p[y][i][0][0],y1+p[y][i][1][0]),SMIN(ty0,INF),

									  ty1=std::min(y0+p[y][i][0][1],y1+p[y][i][1][1]),SMIN(ty1,INF),

									  x0=tx0,x1=tx1,x=f[x][i],y0=ty0,y1=ty1,y=f[y][i];

	return std::min(std::min(h[f[x][0]][0]-dp[x][1]-dp[y][1]+dp[f[x][0]][0]+x1+y1,(ll)h[f[x][0]][1]-std::min(dp[x][0],dp[x][1])-std::min(dp[y][0],dp[y][1])+dp[f[x][0]][1]+std::min(x0,x1)+std::min(y0,y1)),(ll)INF);//错误笔记：防止加的过程中会爆ll

}

int main(){

	read(n),read(m);while(gc()!='\n');

	REP(i,1,n)read(a[i]);

	REP(i,1,n-1)read(x),read(y),Addedge(x,y),Addedge(y,x);

	DP(1);Preprocess();DP2(1);

	REP(i,1,m)read(x),read(ha),read(y),read(hb),abc=Solve(x,ha,y,hb),printf("%lld\n",abc>=INF?-1:abc);

	return flush(),0;

}

巴特西

[BZOJ5466][NOIP2018]保卫王国倍增

最新文章

热门文章

巴特西

[BZOJ5466][NOIP2018]保卫王国 倍增

最新文章

热门文章

[BZOJ5466][NOIP2018]保卫王国倍增