「ZJOI2019」Minmax搜索

传送门

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！

巴特西

「ZJOI2019」Minmax搜索

传送门

Solution

Code

最新文章

热门文章