Uoj 441 保衛(wèi)王國

• 動態(tài) \(dp\) .今天才來寫這個題.
• 設(shè) \(f[u][0/1]\) 表示子樹 \(u\) 中不選/選 \(u\) 時的最小權(quán)值和,顯然有:\(f[u][0]=\sum f[v][1] ,f[u][1]=w[u]+\sum \min(f[v][0],f[v][1])?\) .
• 現(xiàn)在要資瓷修改 \(x\) 的點權(quán) \(w[x]\) ,容易發(fā)現(xiàn)修改后只會影響 \(x\) 到根節(jié)點這一條鏈上的 \(f\) 值.若暴力更新這一條鏈,在樹深度大時,時間復(fù)雜度仍是 \(O(nm)\) 的.考慮使用樹剖來維護(hù),嘗試快速更新信息.
• 由于樹剖后,一個節(jié)點到根節(jié)點的路徑上,輕邊/重鏈都不會超過 \(logn\) 條,可以暴力修改輕兒子的貢獻(xiàn),用數(shù)據(jù)結(jié)構(gòu)來維護(hù)重鏈.那么輕重兒子的信息需要分開存,用 \(g[u][0/1]\) 表示子樹 \(u\) 除去重兒子的子樹后, 不選/選 \(u\) 時的最小權(quán)值和.
• 轉(zhuǎn)移可以用下面這個轉(zhuǎn)移矩陣表示,這里是 Min-plus matrix multiplication ,即將原來矩陣乘法的乘法換成加法,加法換成取 \(\min?\) .仍然滿足結(jié)合律..(這東西還有其他用法,可以點進(jìn)去看看)

• 用線段樹維護(hù)區(qū)間矩陣乘積即可.

參考

#include<bits/stdc++.h> using namespace std; typedef long long ll; inline ll read() {ll out=0,fh=1;char jp=getchar();while ((jp>'9'||jp<'0')&&jp!='-')jp=getchar();if (jp=='-')fh=-1,jp=getchar();while (jp>='0'&&jp<='9')out=out*10+jp-'0',jp=getchar();return out*fh; } const int MAXN=1e5+10; int n,m; int nx[MAXN<<1],to[MAXN<<1],head[MAXN],cnt=0; inline void addedge(int u,int v) {++cnt;nx[cnt]=head[u];to[cnt]=v;head[u]=cnt;swap(u,v);++cnt;nx[cnt]=head[u];to[cnt]=v;head[u]=cnt; } ll w[MAXN]; ll f[MAXN][2],g[MAXN][2]; int fa[MAXN],mxson[MAXN],siz[MAXN],dep[MAXN],dfn[MAXN],rnk[MAXN],top[MAXN],bot[MAXN],idx=0; void DP(int u,int Fa) {f[u][1]=w[u];for(int i=head[u];i;i=nx[i]){int v=to[i];if(v==Fa)continue;DP(v,u);f[u][0]+=f[v][1];f[u][1]+=min(f[v][0],f[v][1]);} } void dfs1(int u,int Fa) {fa[u]=Fa;siz[u]=1;dep[u]=dep[Fa]+1;for(int i=head[u];i;i=nx[i]){int v=to[i];if(v==Fa)continue;dfs1(v,u);siz[u]+=siz[v];if(siz[v]>siz[mxson[u]])mxson[u]=v;} } void dfs2(int u,int tp) {top[u]=tp;dfn[u]=++idx;rnk[idx]=u;if(mxson[u])dfs2(mxson[u],tp);for(int i=head[u];i;i=nx[i]){int v=to[i];if(v!=fa[u] && v!=mxson[u])dfs2(v,v);} } const ll inf=1e18; struct node{ll v[2][2];int l,r;node(){v[0][0]=v[0][1]=v[1][0]=v[1][1]=inf;}node operator * (const node &rhs) const{node res;res.l=l,res.r=rhs.r;for(int k=0;k<2;++k)for(int i=0;i<2;++i)for(int j=0;j<2;++j)res.v[i][j]=min(res.v[i][j],v[i][k]+rhs.v[k][j]);return res;} }; node val[MAXN]; struct SegTree{ node Tree[MAXN<<2];#define root Tree[o]#define lson Tree[o<<1]#define rson Tree[o<<1|1]inline void pushup(int o){root=lson*rson;}void BuildTree(int o,int l,int r){root.l=l,root.r=r;if(l==r){int u=rnk[l],g[2];g[0]=0,g[1]=w[u];for(int i=head[u];i;i=nx[i]){int v=to[i];if(v==fa[u] || v==mxson[u])continue;g[0]+=f[v][1];g[1]+=min(f[v][0],f[v][1]);}root.v[0][0]=inf,root.v[0][1]=g[0];root.v[1][0]=root.v[1][1]=g[1];val[l]=root;return;}int mid=(l+r)>>1;BuildTree(o<<1,l,mid);BuildTree(o<<1|1,mid+1,r);pushup(o);}void update(int o,int pos){int l=root.l,r=root.r;if(l==r){root=val[pos];return;}int mid=(l+r)>>1;if(pos<=mid)update(o<<1,pos);elseupdate(o<<1|1,pos);pushup(o);}node query(int o,int L,int R){int l=root.l,r=root.r;if(L<=l && r<=R)return root;int mid=(l+r)>>1;if(R<=mid)return query(o<<1,L,R);if(L>mid)return query(o<<1|1,L,R);return query(o<<1,L,R)*query(o<<1|1,L,R);} }T; node query(int x) {return T.query(1,dfn[x],dfn[bot[x]]); } ll getans() {node s=query(1);return min(s.v[0][1],s.v[1][1]); } void upd(int x,ll nv) {val[dfn[x]].v[1][0]-=w[x]-nv;val[dfn[x]].v[1][1]-=w[x]-nv;w[x]=nv;while(x){node org=query(top[x]);T.update(1,dfn[x]);node nx=query(top[x]);x=fa[top[x]];val[dfn[x]].v[0][1]+=nx.v[1][1]-org.v[1][1];val[dfn[x]].v[1][0]+=min(nx.v[1][1],nx.v[0][1])-min(org.v[1][1],org.v[0][1]);val[dfn[x]].v[1][1]=val[dfn[x]].v[1][0];} } void solve(int x1,int t1,int x2,int t2) {if(t1==0 && t2==0 && (fa[x1]==x2 || fa[x2]==x1))return void(puts("-1"));ll v1=w[x1],v2=w[x2];upd(x1,v1+(t1?-inf:inf));upd(x2,v2+(t2?-inf:inf));ll res=getans();res+=t1?inf:0;res+=t2?inf:0;printf("%lld\n",res);upd(x1,v1);upd(x2,v2); } char tip[5]; signed main() {//freopen("tx.in","r",stdin);n=read(),m=read();scanf("%s",tip);for(int i=1;i<=n;++i)w[i]=read();for(int i=1;i<n;++i){int u=read(),v=read();addedge(u,v);}DP(1,0);dfs1(1,0);dfs2(1,1);for(int i=1;i<=n;++i){if(i==top[i]){int t=i;while(mxson[t])t=mxson[t];bot[i]=t;}}T.BuildTree(1,1,n);while(m--){int a=read(),b=read(),c=read(),d=read();solve(a,b,c,d);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/jklover/p/10466278.html

總結(jié)

以上是生活随笔為你收集整理的Uoj 441 保卫王国的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。