自动搬运

查看原文

来自洛谷，原作者为

	Fuyuki 闲云遮月，清风袭花

搬运于2025-08-24 22:09:00，当前版本为作者最后更新于2020-07-01 15:30:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

直接求 $w(S)=k$ 的方案数很困难，考虑放宽条件求 $w(S)\leq k$ 的方案数，即计算修改代价不大于 $k$ 的方案数。

设 $u$ 的权值为 $dp_u$，根的权值为 $dp_1=W$。如果有 $W\in S$，则只需要花费 $1$ 的代价将 $W$ 权值修改掉。这种情况是平凡的，所以接下来默认 $w\notin S$。

在整棵树上，满足 $dp_u=W$ 的所有节点 $u$ 构成了一条从叶子到根的链。如果这根链上有任何一个节点的权值发生改变，那么根的权值也会发生改变。

考虑每个叶子 $x$ 和 $W$ 的 $lca$，如果 $lca$ 的深度为奇数，那么只有当 $x>W$ 的时候，$W$ 的权值才可能因为 $x$ 发生改变。换言之，如果 $x\in S$，则此时将 $x$ 修改为 $x>W$ 一定比 $x<W$ 更优。

因此，如果当前代价为 $k$，则根据与 $W$ 的 $lca$ 的深度，可以贪心地直接确定每个节点的权值。

将链上的边断掉，可以对每个联通块求解有多少种方案会使得子树中存在的权值 $W$ 在当前位置被替换掉。设 $f_u$ 表示使得 $dp_u<W$ 的方案数，$cnt_u$ 表示以 $u$ 为根的子联通块内的总方案数（即 $2$ 的叶子个数次方）。链上只要有一个节点能替换掉 $W$ 就是合法的，因此合法的方案数为总方案数减去所有不合法的方案数之积：

$$ans=sum-\prod_{dp_u=W}([dep_u\operatorname{mod} 2\equiv 1]f_u+[dep_u\operatorname{mod} 2\equiv 0](cnt_u-f_u)) $$

计算 $f_u$ 的时候，注意到不存在权值为 $W$ 的叶子，因此使得 $dp_u>W$ 的方案数可以简单表示为 $cnt_u-f_u$ 。转移也可以写出来了：

$$f_u=\begin{cases}\prod_{v\in son_u} f_v&dep_u\equiv 1\pmod{2}\\ cnt_u-\prod_{v\in son_u} (cnt_v-f_v)&dep_u\equiv 0\pmod{2} \end{cases} $$

设 $g_u=cnt-f_u$ 当 $dep_u\equiv 1\pmod{2}$，$g_u=f_u$ 当 $dep_u\equiv 0\pmod{2}$，那么就有：

$$ans=sum-\prod_{dp_u=W}(cnt_u-g_u)$$ $$g_u=cnt_u-\prod_{v\in son_u}g_v$$

至此，枚举最大代价的限制 $k$，可以 $O(n)$ 地计算答案的数量。

注意到将 $k$ 在 $1\sim n$ 中枚举的时候，每个叶子的 $f$ 最多发生 $1$ 次改变，这启发我们动态维护 $dp$ 的过程。

重链剖分之后，有：

$$g_u=cnt_u+(-\prod_{v\in light_u}g_v)g_{weight_u}$$

可以发现这是一个 $a_i=b+ca_{i+1}$ 的形式，并且满足结合律，所以可以直接照搬动态 $dp$ 的做法。

在每次跳轻边的时候，都需要一次求逆，因此哪怕你写了全局平衡二叉树，复杂度依旧会达到 $O(nlog^2n)$。

维护轻儿子的积时，因为可能出现乘 $0$，除 $0$ 的情况，所以需要一个额外的数组来统计 $0$ 的个数。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define lc ls[p]
#define rc rs[p]
#define I inline int
#define V inline void
#define ll long long int
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define REP(u) for(int i=h[u],v;v=e[i].t;i=e[i].n)if(v!=pre[u])
const int N=2e5+1,mod=998244353,INF=0x3f3f3f3f,sgn[2]={-1,1};
V cmin(int&x,int y){if(y-x>>31)x=y;}
V cmax(int&x,int y){if(x-y>>31)x=y;}
V check(int&x){x-=mod,x+=x>>31&mod;}
int sum[N],zero[N];
int n,m,L,R,W,tot,qwq,bas=1;
int h[N],dep[N],dp[N],ans[N],co[N];
int siz[N],wes[N],tmp[N],pre[N],cnt[N];
int ls[N],rs[N],fa[N],id[N],top[N],d[N];
struct node{
	int b,c;
	node(int x=0,int y=1){b=x,c=y;}
	node operator+(const node&u)const{
		return(node){int((1ll*c*u.b+b)%mod),int(1ll*c*u.c%mod)};
	}
}a[N],t[N];
struct edge{int t,n;}e[N<<1];
V add_edge(int x,int y){
	e[++tot]=(edge){y,h[x]},h[x]=tot,d[x]++;
	e[++tot]=(edge){x,h[y]},h[y]=tot,d[y]++;
}
I Pow(ll t,int x,ll s=1){for(;x;x>>=1,t=t*t%mod)if(x&1)s=s*t%mod;return s;}
V input(){
	scanf("%d%d%d",&n,&L,&R);int x,y;
	FOR(i,2,n)scanf("%d%d",&x,&y),add_edge(x,y);
}
I leaf(int u){return u>1&&d[u]==1;}
V dfs0(int u){
	dp[u]=(~dep[u]&1)*INF;
	REP(u)dep[v]=dep[u]+1,pre[v]=u,dfs0(v),(dep[u]&1?cmax:cmin)(dp[u],dp[v]);
	if(leaf(u))dp[u]=u;
}
V dfs1(int u){
	siz[u]=1,cnt[u]=1+leaf(u),check(bas<<=leaf(u));
	REP(u)if(dp[v]!=W){
		dep[v]=dep[u]+1,pre[v]=u,dfs1(v),siz[u]+=siz[v];
		if(cnt[u]=1ll*cnt[u]*cnt[v]%mod,siz[v]>siz[wes[u]])wes[u]=v;
	}
	REP(u)if(dp[v]==W)dfs1(v);
}
V upd(int p){t[p]=t[lc]+a[p]+t[rc];}
V add(int x,int w){
	if(w)sum[x]=1ll*sum[x]*w%mod,a[x].c=1ll*a[x].c*w%mod;
	else if(!zero[x]++)a[x].c=0;
}
V del(int x,int w){
	if(w=Pow(w,mod-2))sum[x]=1ll*sum[x]*w%mod,a[x].c=1ll*a[x].c*w%mod;
	else if(!--zero[x])a[x].c=sum[x];
}
V build(int&p,int L,int R){
	if(L>R)return;
	int sum=0,now=0,x;
	FOR(i,L,R)sum+=siz[tmp[i]];
	for(x=L,sum>>=1;(now+=siz[tmp[x]])<sum;x++);
	p=tmp[x],build(lc,L,x-1),build(rc,x+1,R),fa[lc]=fa[rc]=p;
}
V init(int p){if(p)init(lc),init(rc),upd(p);}
V dfs2(int u,int p){
	id[tmp[++tot]=u]=m,siz[u]-=siz[wes[u]],sum[u]=1,co[u]=p;
	if(wes[u])a[u]={cnt[u],sum[u]=mod-1},dfs2(wes[u],p),top[u]=top[wes[u]];
	else{
		if(leaf(u)&&(a[u]={(u<=W)+(u<W),0},dep[u]&1))a[u].b=cnt[u]-a[u].b;
		build(top[u],1,tot),tot=0;
	}
	REP(u)if(v!=wes[u]&&dp[v]!=W)dfs2(v,p),fa[top[v]]=u,init(top[v]),add(u,t[top[v]].b);
}
V build(int u){
	dfs2(m=u,sgn[dep[u]&1]),init(top[u]),add(0,(cnt[u]+mod-t[top[u]].b)%mod);
	REP(u)if(dp[v]==W)build(v);
}
V init(){dfs0(dep[1]=1),W=dp[1],dfs1(sum[0]=1),tot=0,build(m=1);}
V modify(int p){
	int x=id[p];
	del(0,cnt[x]+mod-t[top[x]].b);
	for(a[p]={1,0};p;p=fa[p]){
		if(p==top[p]&&fa[p])del(fa[p],t[p].b);
		upd(p);
		if(p==top[p]&&fa[p])add(fa[p],t[p].b);
	}
	add(0,cnt[x]+mod-t[top[x]].b);
}
V work(){
	FOR(i,1,n){
		check(ans[i]=bas+mod-a[0].c);
		if(W+i<=n&&leaf(W+i)&&co[W+i]<0)modify(W+i);
		if(W-i>=2&&leaf(W-i)&&co[W-i]>0)modify(W-i);
	}
	ans[0]=0,ans[n]=bas-1;
	ROF(i,n,1)check(ans[i]+=mod-ans[i-1]);
	FOR(i,L,R)cout<<ans[i]<<' ';
}
int main(){
	input();
	init();
	work();
	return 0;
}
```

起码 10 个月没写动态 dp 了，写了好久