UOJ#468. 【ZJOI2019】Minimax搜索 動態(tài)DP
原文鏈接www.rzrgm.cn/zhouzhendong/p/UOJ468.html
前言
毒瘤題
題解
首先，將問題稍加轉(zhuǎn)化，將“等于k”轉(zhuǎn)化為“小于等于k”減去“小于k”。
然后，考慮在有一個變化量限制k時，所有的葉子會怎樣變化。
我們稱原本根的權(quán)值對應(yīng)的節(jié)點到根的路徑為“主鏈”，那么，只要主鏈的任何一個節(jié)點的權(quán)值發(fā)生變化，那么根節(jié)點權(quán)值就發(fā)生變化。
我們稱一個主鏈上的節(jié)點的在主鏈上的兒子為“主兒子”。
對于主鏈上的一個節(jié)點，假設(shè)他深度為奇數(shù)，那么他的所有子樹中，除了主兒子所在子樹以外的所有葉子節(jié)點都會加上k。否則，假設(shè)他深度為偶數(shù)，那么這些葉子節(jié)點會減去k。
于是，接下來我們就可以得到一個 \(O(n)\) 的 DP 方法。即
對于深度為奇數(shù)的主鏈的子樹， \(dp[x][0]\)、\(dp[x][1]\) 分別表示在子樹x的所有葉子節(jié)點集合操作時，有 \(dp[x][1]\) 個集合可以使得 x 的權(quán)值大于 1 號點原先的權(quán)值，有 \(dp[x][0]\) 個不能。
對于深度為偶數(shù)的主鏈的子樹， \(dp[x][1]\)、\(dp[x][0]\) 分別表示在子樹x的所有葉子節(jié)點集合操作時，有 \(dp[x][1]\) 個集合可以使得 x 的權(quán)值小于 1 號點原先的權(quán)值，有 \(dp[x][1]\) 個不能。
請讀者自行列出 DP 轉(zhuǎn)移。
事實上，這種 DP 狀態(tài)是可以簡化的。由于對于一個 x，\(dp[x][0]+dp[x][1]\) 是固定的，所以我們只需要記一個。雖然這不影響得分。
至此，我們得到了一個單次 DP \(O(n)\)，總時間復(fù)雜度 \(O((R-L)\cdot n)\) 的做法。
我們發(fā)現(xiàn)，當(dāng)k的值從小到大不斷變大時，只會有 \(O(n)\) 個葉子的 DP 值發(fā)生變化，每次變化會影響它到根的路徑。
簡單分析即可發(fā)現(xiàn)這里可以用動態(tài)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;
}
浙公網(wǎng)安備 33010602011771號