为什么我怎么看都只会10pts？再看还是只会50~70？只会O(n2(R-L+1))/O(nlogn(R-L+1))……一眼看动态DP可还是不会做……
根节点的答案是叶子传上来的，所以对于L=R的数据，可以直接枚举需要±n的叶子节点个数num，然后答案就是2num，每次枚举时重新扫描一下就是O(n2(R-L+1))。然后发现可以动态DP，不需要每次O(n)，于是可以优化到O(nlogn(R-L+1))。
然后可以发现若叶子x为答案，叶子x到根的链上的DP值都为x，而一旦更改，要么更改根的值，要么更改链上任意一个点的值，显然更改链上最优。因此只要求出这条链上权值不变的方案数，再用总方案数减去这个方案数就是这条答案链的方案数。所以根据前面说的50/70分思想，每次只需更改一个叶子，考虑动态DP，然后轻重链剖分，每次沿着重链往上跳即可。时间复杂度O((R-L)log2n)
#include<bits/stdc++.h> using namespace std; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const int N=2e5+7,mod=998244353; struct mat{int a,b;}a[N],tr[N<<2]; mat operator*(mat a,mat b){return(mat){1ll*a.a*b.a%mod,(1ll*a.a*b.b+a.b)%mod};} int n,L,R,ret=1,cnt,pw[N],fa[N],dep[N],val[N],flag[N],q[N][3],s[N],f[N]; int son[N],sz[N],pos[N],top[N],dfn[N],ed[N],rt[N],ans[N]; vector<int>G[N]; int qpow(int a,int b) { int ret=1; while(b) { if(b&1)ret=1ll*ret*a%mod; a=1ll*a*a%mod,b>>=1; } return ret; } void dfs1(int u) { dep[u]=dep[fa[u]]+1,sz[u]=1,val[u]=(dep[u]&1)?1:n,s[u]=1; bool leaf=1; for(int i=0;i<G[u].size();i++) if(G[u][i]!=fa[u]) { leaf=0,fa[G[u][i]]=u; dfs1(G[u][i]); sz[u]+=sz[G[u][i]],s[u]=1ll*s[u]*s[G[u][i]]%mod; val[u]=(dep[u]&1)?max(val[u],val[G[u][i]]):min(val[u],val[G[u][i]]); if(sz[G[u][i]]>sz[son[u]])son[u]=G[u][i]; } if(leaf)val[u]=u,s[u]=2;else a[u].b=s[u]; } void dfs2(int u,int tp) { top[u]=tp,dfn[u]=++cnt,pos[cnt]=u; if(son[u])dfs2(son[u],tp);else ed[tp]=cnt; for(int i=0;i<G[u].size();i++) if(G[u][i]!=son[u]&&G[u][i]!=fa[u])dfs2(G[u][i],G[u][i]); } void dp(int u,int rt1) { rt[u]=rt1; bool leaf=0; int ret=mod-1; for(int i=0;i<G[u].size();i++) if(G[u][i]!=fa[u]) { leaf=1,dp(G[u][i],rt1); if(G[u][i]!=son[u])ret=1ll*ret*f[G[u][i]]%mod; } if(!leaf) { if(flag[rt1]) { f[u]=a[u].a=(dep[u]&1)?2-(u<=val[1]):(u<=val[1]); if(u<=val[1])q[val[1]-u][++q[val[1]-u][0]]=u; } else{ f[u]=a[u].a=(dep[u]&1)?(u>=val[1]):2-(u>=val[1]); if(u>=val[1])q[u-val[1]][++q[u-val[1]][0]]=u; } return; } a[u].a=ret,f[u]=(1ll*ret*f[son[u]]+s[u])%mod; } void dfs(int u) { for(int i=0;i<G[u].size();i++) if(G[u][i]!=fa[u]) { if(val[u]==val[G[u][i]])dfs(G[u][i]); else{ dfs2(G[u][i],G[u][i]); flag[G[u][i]]=(dep[u]&1); dp(G[u][i],G[u][i]); ret=1ll*ret*f[G[u][i]]%mod; } } } void build(int l,int r,int rt) { if(l==r){tr[rt]=a[pos[l]];return;} int mid=l+r>>1; build(lson),build(rson); tr[rt]=tr[rt<<1]*tr[rt<<1|1]; } void update(int k,int v,int l,int r,int rt) { if(l==r){tr[rt].a=v;return;} int mid=l+r>>1; if(k<=mid)update(k,v,lson);else update(k,v,rson); tr[rt]=tr[rt<<1]*tr[rt<<1|1]; } mat query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R)return tr[rt]; int mid=l+r>>1; if(L<=mid&&R>mid)return query(L,R,lson)*query(L,R,rson); if(L<=mid)return query(L,R,lson); if(R>mid)return query(L,R,rson); } void modify(int u) { int rt1=rt[u]; ret=1ll*ret*qpow(f[rt1],mod-2)%mod; update(dfn[u],(flag[rt1]^(dep[u]&1))?2:0,1,cnt,1); while(top[u]!=rt1) { mat p=query(dfn[top[u]],ed[top[u]],1,cnt,1); int t=f[top[u]],sum=(p.a+p.b)%mod; f[top[u]]=sum,u=fa[top[u]],a[u].a=1ll*a[u].a*qpow(t,mod-2)%mod*sum%mod; update(dfn[u],a[u].a,1,cnt,1); } mat p=query(dfn[rt1],ed[rt1],1,cnt,1); f[rt1]=(p.a+p.b)%mod,ret=1ll*ret*f[rt1]%mod; } int main() { scanf("%d%d%d",&n,&L,&R); pw[0]=1;for(int i=1;i<=n;i++)pw[i]=2ll*pw[i-1]%mod; for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x); dfs1(1),dfs(1); build(1,cnt,1); ans[n]=s[1]-1; for(int i=n-1;i;i--) { for(int j=1;j<=q[i][0];j++)modify(q[i][j]); ans[i]=(s[1]-ret+mod)%mod; } for(int i=L;i<=R;i++)printf("%d ",(ans[i]-ans[i-1]+mod)%mod); }