「ZJOI2019」Minmax搜索

痛定思痛。 2021-11-17 15:22 315阅读 0赞

## [ 传送门 ][Link 1] ##

## **Solution**  ##

> 叶子节点的变化区间是连续的，可得知非叶子节点的权值变化区间也是连续的
> 
> 由此可知，\\(W\\)的变化值的可行域也是连续的，所以只需要看它能否变为\\(W+1\\)或\\(W-1\\)
> 
> 对于答案，可以先求消耗能量不超过\\(k\\)的集合数\\(ans\_k\\)，再进行查分
> 
> 发现\\(ans\_1=2^\{m-1\},ans\_n=2^\{m\}-1\\)
> 
> 首先发现，如果要将\\(W\\)的值\\(+1\\)，那么只会去动那些\\(\\leq W\\)的的节点，让它们的权值变大
> 
> 类似的，我们发现处理的两类节点无交，所以可以分别求出可以使得\\(W\\)加一或者减一的概率
> 
> 因为通过减少较大权值的点的权值的办法都可以被上面的方法取代
> 
> 当且仅当包含了\\(W\\)点，只需要耗费\\(1\\)的能量
> 
> 接下来考虑不包含\\(W\\)点的情况，假如我们要求\\(ans\_k\\)
> 
> 把\\(<W\\)的节点称作小节点，\\(>W\\)的节点称作大结点
> 
> 设\\(f\_i\\)表示只改动小节点的值但是\\(i\\)点权值仍然\\(\\leq W\\)的概率
> 
> 奇数点：  
> \\\[ f\_u=\\prod f\_v \\\]  
> 偶数点：  
> \\\[ f\_u=1-\\prod(1-f\_v) \\\]  
> 设\\(g\_i\\)表示可以通过改变大结点来使得\\(i\\)点权值\\(<W\\)的概率，转移与\\(f\_i\\)相似
> 
> 所以，得到  
> \\\[ ans\_k=2^\{m-1\}(1-f\_1(1-g\_1))+2^\{m-1\} \\\]  
> 其中\\(f\_1(1-g\_1)\\)表示的是根节点权值保持不变的概率
> 
> \\(k\\)每递增\\(1\\)最多改变两个叶子点的\\(dp\\)值
> 
> 动态\\(dp\\)实现
> 
> 对于奇偶深度的叶子问题
> 
> 可以使得偶层节点\\(f\_i’=1-f\_i,g\_i'=1-g\_i\\)
> 
> 这样，我们都可以通过这样来转移了  
> \\\[ f\_u=\\prod (1-f\_v)\\\\g\_u=\\prod(1-g\_v) \\\]  
> 也是毒瘤题。。。
> 
> 有可能会除以\\(0\\)，所以记录一下乘了\\(0\\)的个数，和不含\\(0\\)的其它项的积
> 
> --------------------
> 
> 突然发现自己忘记ddp的做法，不妨重温一下
> 
> 首先我们设了函数\\(f\\)和\\(g\\)，(和上述函数无关）
> 
> 分别表示算了重儿子和没算重儿子的答案
> 
> 在本题中，它们的转移如下
> 
> 如果是叶子节点，或者某个重链的链底
> 
> 则有\\(g\_i=f\_i\\)
> 
> 然后有（序号表示的是距离链头的距离\\(+1\\)）  
> \\\[ f\_1=(1-f\_2)g\_1 \\\\f\_2=(1-f3)g\_2 \\\\...\\\\f\_n=g\_n\\\\ f\_1=g\_1-g\_1g\_2+g\_1g\_3g\_4-...+(-1)^\{n+1\}(g\_1g\_2...g\_n) \\\]  
> 由此可以发现，在维护那个线段树区间乘法的同时，还需要维护一个如上的\\(Sum\\)值
> 
> 总结：
> 
> 之前做ddp的时候，是使用线段树维护一个链的转移矩阵的积，并不能直接求出链顶的答案
> 
> 而在此题，我们直接将修改链底的答案，并更新进线段树，通过计算直接得到链顶的答案，线段树可以直接取代\\(f\\)数组
> 
> 另外不需要建立庞大的所有点的线段树
> 
> 可以分别对每条链建一棵，这样就只需要一个\\(Modify\\)，而不用\\(Query\\)
> 
> 最后，这真是一道毒瘤题

## **Code ** ##

#include<bits/stdc++.h> #define ll long long using namespace std; #define reg register inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } const int P=998244353,MN=2e5+5; int Mul(int x,int y){return (1ll*x*y)%P;} int Add(int x,int y){return (x+y)%P;} int fpow(int x,int m){int r=1;for(;m;m>>=1,x=Mul(x,x))if(m&1)r=Mul(r,x);return r;} struct node { int a,cnt; node(){a=1,cnt=0;} node(int a,int cnt):a(a),cnt(cnt){} void mul(node o){a=Mul(a,o.a),cnt+=o.cnt;} void div(node o){a=Mul(a,fpow(o.a,P-2)),cnt-=o.cnt;} int val(){return cnt?0:a;} }f[MN],g[MN]; node _(int x){x%=P;return x?node(x,0):node(1,1);} struct edge{int to,nex;}e[MN<<1]; bool lf[MN]; int hr[MN],en,mx[MN],siz[MN],top[MN],bot[MN],fa[MN],dfn[MN],fdfn[MN],dep[MN],dind=0,leaf=1; int n,W,ans[MN],F[MN],G[MN]; inline void ins(int x,int y) { e[++en]=(edge){y,hr[x]};hr[x]=en; e[++en]=(edge){x,hr[y]};hr[y]=en; } void rw(int &x,int y,int z){z?x=max(x,y):x=min(x,y);} int dfs1(int x,int f,int d) { register int i;fa[x]=f;siz[x]=1;dep[x]=d; int res=d&1?0:0x3f3f3f3f; for(i=hr[x];i;i=e[i].nex)if(e[i].to^f) { rw(res,dfs1(e[i].to,x,d+1),d&1); siz[x]+=siz[e[i].to],siz[e[i].to]>siz[mx[x]]?mx[x]=e[i].to:0; } if(siz[x]==1){lf[x]=1;leaf=(leaf<<1)%P;return x;} return res; } int rt[MN],ls[MN<<2],rs[MN<<2],sum_f[MN<<2],sum_g[MN<<2],prd_f[MN<<2],prd_g[MN<<2],tt; void Build(int &x,int l,int r); void dfs2(int x,int tp) { fdfn[dfn[x]=++dind]=x;top[x]=tp; register int i;if(mx[x])dfs2(mx[x],tp); for(i=hr[x];i;i=e[i].nex)if((e[i].to^fa[x])&&(e[i].to^mx[x]))dfs2(e[i].to,e[i].to); if(mx[x]) { F[x]=G[x]=1; for(i=hr[x];i;i=e[i].nex)if(e[i].to^fa[x]) { F[x]=Mul(F[x],(1+P-F[e[i].to])); G[x]=Mul(G[x],(1+P-G[e[i].to])); if(e[i].to^mx[x]) f[x].mul(_(1+P-F[e[i].to])),g[x].mul(_(1+P-G[e[i].to])); } } else { F[x]=(x>W)^(dep[x]&1),G[x]=(x>=W)^(dep[x]&1); bot[top[x]]=x; f[x]=_((x>W)^(dep[x]&1));g[x]=_((x>=W)^(dep[x]&1)); } if(x==tp) Build(rt[x],dfn[x],dfn[bot[x]]); } void up(int x,int l) { sum_f[x]=Add(sum_f[ls[x]],Mul((l&1?P-prd_f[ls[x]]:prd_f[ls[x]]),sum_f[rs[x]])); prd_f[x]=Mul(prd_f[ls[x]],prd_f[rs[x]]); sum_g[x]=Add(sum_g[ls[x]],Mul((l&1?P-prd_g[ls[x]]:prd_g[ls[x]]),sum_g[rs[x]])); prd_g[x]=Mul(prd_g[ls[x]],prd_g[rs[x]]); } void update(int x,int a){sum_f[x]=prd_f[x]=f[a].val();sum_g[x]=prd_g[x]=g[a].val();} void Build(int &x,int l,int r) { x=++tt; if(l==r)return(void)(update(x,fdfn[l])); int mid=(l+r)>>1; Build(ls[x],l,mid);Build(rs[x],mid+1,r); up(x,mid-l+1); } void Modify(int x,int l,int r,int a) { if(l==r)return(void)(update(x,fdfn[l])); int mid=(l+r)>>1; a<=mid?Modify(ls[x],l,mid,a):Modify(rs[x],mid+1,r,a); up(x,mid-l+1); } #define o top[x] void solve_f(int x) { if(fa[o]) f[fa[o]].div(_(P+1-sum_f[rt[o]])); Modify(rt[o],dfn[o],dfn[bot[o]],dfn[x]); if(fa[o]) f[fa[o]].mul(_(P+1-sum_f[rt[o]])),solve_f(fa[o]); } void solve_g(int x) { if(fa[o]) g[fa[o]].div(_(P+1-sum_g[rt[o]])); Modify(rt[o],dfn[o],dfn[bot[o]],dfn[x]); if(fa[o]) g[fa[o]].mul(_(P+1-sum_g[rt[o]])),solve_g(fa[o]); } int main() { int L,R; n=read();L=read();R=read(); register int i,j; for(i=1;i<n;++i) j=read(),ins(j,read()); W=dfs1(1,0,1);dfs2(1,1); ans[1]=leaf=Mul(leaf,(P+1)>>1); for(i=2;i<n;++i) { if(W+1-i>=1&&lf[W+1-i]) f[W+1-i]=_(P+1>>1),solve_f(W+1-i); if(W+i-1<=n&&lf[W+i-1]) g[W+i-1]=_(P+1>>1),solve_g(W+i-1); ans[i]=Mul(Add(Mul(P-sum_f[rt[1]],P+1-sum_g[rt[1]]),2),leaf); } ans[n]=Add(Mul(leaf,2),P-1); for(i=L;i<=R;++i) printf("%d ",Add(ans[i],P-ans[i-1])); return 0; }

--------------------

Blog来自**PaperCloud**，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/11241741.html

[Link 1]: https://loj.ac/problem/3044