UOJ#468. 【ZJOI2019】Minimax搜索动态DP

绝地灬酷狼 2023-08-17 16:21 108阅读 0赞

原文链接www.cnblogs.com/zhouzhendong/p/UOJ468.html

# 前言 #

毒瘤题

# 题解 #

首先，将问题稍加转化，将“等于k”转化为“小于等于k”减去“小于k”。

然后，考虑在有一个变化量限制k时，所有的叶子会怎样变化。

我们称原本根的权值对应的节点到根的路径为“主链”，那么，只要主链的任何一个节点的权值发生变化，那么根节点权值就发生变化。

我们称一个主链上的节点的在主链上的儿子为“主儿子”。

对于主链上的一个节点，假设他深度为奇数，那么他的所有子树中，除了主儿子所在子树以外的所有叶子节点都会加上k。否则，假设他深度为偶数，那么这些叶子节点会减去k。

于是，接下来我们就可以得到一个 \\(O(n)\\) 的 DP 方法。即

对于深度为奇数的主链的子树， \\(dp\[x\]\[0\]\\)、\\(dp\[x\]\[1\]\\) 分别表示在子树x的所有叶子节点集合操作时，有 \\(dp\[x\]\[1\]\\) 个集合可以使得 x 的权值大于 1 号点原先的权值，有 \\(dp\[x\]\[0\]\\) 个不能。

对于深度为偶数的主链的子树， \\(dp\[x\]\[1\]\\)、\\(dp\[x\]\[0\]\\) 分别表示在子树x的所有叶子节点集合操作时，有 \\(dp\[x\]\[1\]\\) 个集合可以使得 x 的权值小于 1 号点原先的权值，有 \\(dp\[x\]\[1\]\\) 个不能。

请读者自行列出 DP 转移。

事实上，这种 DP 状态是可以简化的。由于对于一个 x，\\(dp\[x\]\[0\]+dp\[x\]\[1\]\\) 是固定的，所以我们只需要记一个。虽然这不影响得分。

至此，我们得到了一个单次 DP \\(O(n)\\)，总时间复杂度 \\(O((R-L)\\cdot n)\\) 的做法。

我们发现，当k的值从小到大不断变大时，只会有 \\(O(n)\\) 个叶子的 DP 值发生变化，每次变化会影响它到根的路径。

简单分析即可发现这里可以用动态DP来维护。

于是我们就得到了一个 \\(O(n\\log ^ 2 n)\\) 的做法。

注意维护的时候可以会遇到乘0和除0的情况，注意特判。

# 代码 #

#pragma GCC optimize("Ofast","inline") #include <bits/stdc++.h> #define clr(x) memset(x,0,sizeof x) #define For(i,a,b) for (int i=(a);i<=(b);i++) #define Fod(i,b,a) for (int i=(b);i>=(a);i--) #define pb(x) push_back(x) #define mp(x,y) make_pair(x,y) #define fi first #define se second #define next Next #define outval(x) cerr<<#x" = "<<x<<endl #define outtag(x) cerr<<"-----------------"#x"-----------------\n" #define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\ For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair <int,int> pii; LL read(){ LL x=0,f=0; char ch=getchar(); while (!isdigit(ch)) f=ch=='-',ch=getchar(); while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return f?-x:x; } const int N=200005,mod=998244353; int Pow(int x,int y){ int ans=1; for (;y;y>>=1,x=(LL)x*x%mod) if (y&1) ans=(LL)ans*x%mod; return ans; } void Add(int &x,int y){ if ((x+=y)>=mod) x-=mod; } void Del(int &x,int y){ if ((x-=y)<0) x+=mod; } int Add(int x){ return x>=mod?x-mod:x; } int Del(int x){ return x<0?x+mod:x; } int n,qL,qR; vector <int> e[N]; int depth[N],size[N],son[N],val[N]; int fa[N],leaf[N],clf[N],pw2[N],clf2[N]; int fun(int k,int a,int b){ return k&1?max(a,b):min(a,b); } void dfs(int x,int pre,int d){ depth[x]=d,size[x]=1,son[x]=0,fa[x]=pre; if (e[x].size()==1&&d>1) val[x]=x,leaf[x]=clf[x]=1; else val[x]=d&1?0:n; for (auto y : e[x]) if (y!=pre){ dfs(y,x,d+1); clf[x]+=clf[y]; size[x]+=size[y]; val[x]=fun(d,val[x],val[y]); if (!son[x]||size[y]>size[son[x]]) son[x]=y; } } int next[N],fad[N]; void dfs2(int x,int d){ fad[x]=d; for (auto y : e[x]) if (y!=fa[x]&&y!=next[x]) dfs2(y,d); } void GetNext(){ int x=val[1]; for (int y=fa[x];y;x=y,y=fa[x]) next[y]=x,dfs2(y,depth[y]); } int top[N],I[N],aI[N],Time=0; void GetTop(int x,int tp){ top[x]=tp,I[x]=++Time,aI[Time]=x; if (son[x]&&son[x]!=next[x]) GetTop(son[x],tp); for (auto y : e[x]) if (!I[y]) GetTop(y,y); } int ans[N]; int dp[N]; int delta; void DP(int x){ dp[x]=0; if (x==val[1]){ dp[x]=1; return; } if (leaf[x]){ if (fad[x]&1){ dp[x]+=(x+delta>val[1])==(depth[x]&1); dp[x]+=(x>val[1])==(depth[x]&1); } else { dp[x]+=(x-delta>=val[1])==(depth[x]&1); dp[x]+=(x>=val[1])==(depth[x]&1); } return; } dp[x]=1; for (auto y : e[x]) if (y!=fa[x]){ DP(y); if (y!=next[x]) dp[x]=(LL)dp[x]*dp[y]%mod; } dp[x]=Del(pw2[clf2[x]]-dp[x]); } struct int0{ int v,c; int0(){} int0(int _v,int _c){ v=_v,c=_c; } int f(){ return c?0:v; } void operator *= (int x){ if (!x) c++; else v=(LL)v*x%mod; } void operator /= (int x){ if (!x) c--; else v=(LL)v*Pow(x,mod-2)%mod; } }v2[N],now; int0 Get(){ int0 ans=int0(1,0); for (int x=val[1];x;x=fa[x]) ans*=Del(pw2[clf2[x]]-dp[x]); return ans; } struct fuck{ int a,b; fuck(){} fuck(int _a,int _b){ a=_a,b=_b; } friend fuck operator * (fuck x,fuck y){ return fuck((LL)x.a*y.a%mod,((LL)x.a*y.b+x.b)%mod); } int calc(int x){ return ((LL)a*x+b)%mod; } }v[N]; int mxd[N]; namespace Seg{ fuck s[N<<2]; void Build(int rt,int L,int R){ if (L==R) return (void)(s[rt]=v[aI[L]]); int mid=(L+R)>>1,ls=rt<<1,rs=ls|1; Build(ls,L,mid); Build(rs,mid+1,R); s[rt]=s[ls]*s[rs]; } void update(int rt,int L,int R,int x,fuck v){ if (L==R) return (void)(s[rt]=v); int mid=(L+R)>>1,ls=rt<<1,rs=ls|1; if (x<=mid) update(ls,L,mid,x,v); else update(rs,mid+1,R,x,v); s[rt]=s[ls]*s[rs]; } fuck query(int rt,int L,int R,int xL,int xR){ if (R<xL||L>xR) return fuck(1,0); if (xL<=L&&R<=xR) return s[rt]; int mid=(L+R)>>1,ls=rt<<1,rs=ls|1; return query(ls,L,mid,xL,xR)*query(rs,mid+1,R,xL,xR); } } void update(int x){ while (1){ Seg::update(1,1,n,I[x],v[x]); x=top[x]; int f=fa[x]; if (val[x]!=val[1]) v2[f]/=dp[x]; else now/=Del(pw2[clf2[x]]-dp[x]); dp[x]=Seg::query(1,1,n,I[x],I[mxd[x]]).calc(1); if (val[x]!=val[1]) v2[f]*=dp[x],v[f].a=v2[f].f(),x=f; else { now*=Del(pw2[clf2[x]]-dp[x]); break; } } } vector <int> upds[N]; int main(){ n=read(),qL=read(),qR=read(); pw2[0]=1; For(i,1,n) pw2[i]=Add(pw2[i-1]<<1); For(i,1,n-1){ int x=read(),y=read(); e[x].pb(y),e[y].pb(x); } dfs(1,0,1); GetNext(); GetTop(1,1); For(i,1,n) clf2[i]=clf[i]; for (int x=val[1];x;x=fa[x]) clf2[x]-=clf[next[x]]; delta=1,DP(1),now=Get(),ans[1]=Del(pw2[clf[1]]-now.f()); For(x,1,n){ if (leaf[x]) v[x]=fuck(0,dp[x]); else { v2[x]=int0(Del(-1),0); for (auto y : e[x]) if (y!=fa[x]&&y!=next[x]&&y!=son[x]) v2[x]*=dp[y]; v[x]=fuck(v2[x].f(),pw2[clf2[x]]); } } For(x,1,n) if (top[x]==x) mxd[x]=x; For(x,1,n) if (depth[x]>depth[mxd[top[x]]]) mxd[top[x]]=x; Seg::Build(1,1,n); For(i,1,n){ if (!leaf[i]||i==val[1]) continue; if (fad[i]&1){ if (i<val[1]) upds[val[1]-i+1].pb(i); } else { if (i>val[1]) upds[i-val[1]+1].pb(i); } } For(i,2,n-1){ delta=i; for (auto x : upds[i]){ int tmp=0; if (fad[x]&1){ tmp+=(x+delta>val[1])==(depth[x]&1); tmp+=(x>val[1])==(depth[x]&1); } else { tmp+=(x-delta>=val[1])==(depth[x]&1); tmp+=(x>=val[1])==(depth[x]&1); } v[x]=fuck(0,tmp); update(x); } ans[i]=Del(pw2[clf[1]]-now.f()); } ans[n]=Del(pw2[clf[1]]-1); For(i,qL,qR) printf("%d ",Del(ans[i]-ans[i-1])); puts(""); return 0; }

转载于:https://www.cnblogs.com/zhouzhendong/p/UOJ468.html