题目

描述

​ 给出一颗树，定义根节点1的深度为1，其他点深度为父亲深度+1；

​ 如下定义一个点的点权：
​ 1.叶子：为其编号；2.奇数深度：为其儿子编号最大值；3.偶数深度：为其儿子编号最小值；

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

​ 对于一个叶子集合 \(S\) ，你可以修改 $w_i \to w_i \pm C ，i \in S $ ， 称使得根权值改变的最小\(C\)为\(S\)的稳定度；（如果无论如何根都不变规定稳定度为\(n\)）

​ 询问稳定度为 \(i \in [L,R]\) 的有多少个，对每个 \(i\) 依次输出；

范围

​ $2 \le n \le 2 \times 10^5  ,   1 \le L \le R \le n $

题解

  • 由于点权互不相同，所以一定可以找到一条到某个叶子的链：链上的值都是根节点的值，记这个链为\(key\) ，并且顶点的权值改变的充要条件是\(key\)上某个点改变。考虑统计不改变的情况，对\(key\)上每个点分奇偶做一个 \(dp\) 再相乘，可以求出不变方案数，获得了一个 \(O(n(R-L))\) 的算法。

  • 从小到大考虑 \(C\) ,每个叶子的初始值只会改变一次，用\(ddp\)维护即可。注意由于系数有0需要特判一下；

    #include<bits/stdc++.h>
#define mod 998244353
#define ll long long 
#define ls (k<<1)
#define rs (k<<1|1)
#define mk make_pair
#define pir pair<int,int>
#define fi first
#define se second  
#define il inline 
#define rg register 
using namespace std;
const int N=200010;
int n,L,R,o=1,hd[N],d[N],f[N],g[N],col[N],dep[N],lf[N],id[N];
int fa[N],sz[N],sn[N],st[N],tp[N],dn[N],idx,now,ans[N],cnt,tot;
struct Edge{int v,nt;}E[N<<1];
struct data{
  int a,b;
  il data operator +(const data&A)const{
      data ret;
      ret.a=(ll)a*A.a%mod;
      ret.b=((ll)A.b*a%mod+b)%mod;
      return ret;
  }//维护ax+b的迭代；
}tr[N<<2];
il int pw(int x,int y){
  int re=1;x%=mod;
  while(y){
      if(y&1)re=(ll)re*x%mod;
      y>>=1;x=(ll)x*x%mod;
  }
  return re;
} 
pir a[N];int b[N];
il int val(pir A){return A.se?0:A.fi;}
il pir operator +(pir A,int B){if(!B)A.se++;else A.fi=(ll)A.fi*B%mod;return A;}
il pir operator -(pir A,int B){if(!B)A.se--;else A.fi=(ll)A.fi*pw(B,mod-2)%mod;return A;}
//用来处理ax+b系数a为0的情况；
il char gc(){
  static char*p1,*p2,s[1000000];
  if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
  return(p1==p2)?EOF:*p1++;
}
il int rd(){
  int x=0;char c=gc();
  while(c<'0'||c>'9')c=gc();
  while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
  return x;
}
il void adde(int u,int v){
  d[u]++,d[v]++; 
  E[o]=(Edge){v,hd[u]};hd[u]=o++;
  E[o]=(Edge){u,hd[v]};hd[v]=o++;
}
il void Min(int&x,int y){if(x>y)x=y;}
il void Max(int&x,int y){if(x<y)x=y;}
void dfs_pre(int u,int F){
  dep[u]=dep[fa[u]=F]+1;sz[u]=1;
  if(u!=1&&d[u]==1){lf[u]=2;f[u]=dn[u]=u;return;}
  lf[u]=1;f[u]=dep[u]&1?0:n;
  for(rg int i=hd[u];i;i=E[i].nt){
      int v=E[i].v;
      if(v==F)continue;
      dfs_pre(v,u);
      sz[u]+=sz[v];lf[u]=(ll)lf[u]*lf[v]%mod;
      if(sz[sn[u]]<sz[v])sn[u]=v,dn[u]=dn[v];
      if(dep[u]&1)Max(f[u],f[v]);else Min(f[u],f[v]);
  }
}
//以下为朴素dp部分：
//***************************************
void dfs_mn(int u,int T){
  st[++idx]=u;id[u]=idx;
  tp[u]=T;g[u]=1;col[u]=1;
  if(u!=1&&d[u]==1){a[u]=mk(0,0),b[u]=g[u]=(u<=f[1])<<1;return;}
  if(dep[u]&1){
      a[u]=mk(1,0);b[u]=0;
      dfs_mn(sn[u],T);
      g[u]=(ll)g[u]*g[sn[u]]%mod;
      for(rg int i=hd[u];i;i=E[i].nt){
          int v=E[i].v;
          if(v==fa[u]||v==sn[u])continue;
          dfs_mn(v,v);
          g[u]=(ll)g[u]*g[v]%mod;
          a[u]=a[u]+g[v]%mod;
      }
  }else{
      a[u]=mk(1,0);
      dfs_mn(sn[u],T);
      g[u]=(ll)g[u]*(lf[sn[u]]-g[sn[u]]+mod)%mod;
      for(rg int i=hd[u];i;i=E[i].nt){
          int v=E[i].v;
          if(v==fa[u]||v==sn[u])continue;
          dfs_mn(v,v);
          g[u]=(ll)g[u]*(lf[v]-g[v]+mod)%mod;
          a[u]=a[u]+((lf[v]-g[v]+mod)%mod);
      }
      g[u]=(lf[u]-g[u]+mod)%mod;
      b[u]=(lf[u]-(ll)val(a[u])*lf[sn[u]]%mod+mod)%mod;
  }
}
void dfs_mx(int u,int T){
  st[++idx]=u;id[u]=idx;
  tp[u]=T;g[u]=1;col[u]=2;
  if(u!=1&&d[u]==1){a[u]=mk(0,0),b[u]=g[u]=(u>=f[1])<<1;return;}
  if(dep[u]&1){
      a[u]=mk(1,0);
      dfs_mx(sn[u],T);
      g[u]=(ll)g[u]*(lf[sn[u]]-g[sn[u]]+mod)%mod;
      for(rg int i=hd[u];i;i=E[i].nt){
          int v=E[i].v;
          if(v==fa[u]||v==sn[u])continue;
          dfs_mx(v,v);
          g[u]=(ll)g[u]*(lf[v]-g[v]+mod)%mod;
          a[u]=a[u]+(lf[v]-g[v]+mod)%mod;
      }
      g[u]=(lf[u]-g[u]+mod)%mod;
      b[u]=(lf[u]-(ll)val(a[u])*lf[sn[u]]%mod+mod)%mod;
  }else{
      a[u]=mk(1,0);b[u]=0;
      dfs_mx(sn[u],T);
      g[u]=(ll)g[u]*g[sn[u]]%mod;
      for(rg int i=hd[u];i;i=E[i].nt){
          int v=E[i].v;
          if(v==fa[u]||v==sn[u])continue;
          dfs_mx(v,v);
          g[u]=(ll)g[u]*g[v]%mod;
          a[u]=a[u]+g[v]%mod;
      }
  }
}
void dfs_key(int u){
  for(rg int i=hd[u];i;i=E[i].nt){
      int v=E[i].v;
      if(v==fa[u])continue;
      if(f[u]==f[v]){dfs_key(v);continue;}
      if(dep[u]&1)dfs_mn(v,v);else dfs_mx(v,v);
      now=(ll)now*g[v]%mod;
  }
}
//******************************************
il void pushup(int k){tr[k]=tr[ls]+tr[rs];}
void build(int k,int l,int r){
  if(l==r){tr[k]=(data){val(a[st[l]]),b[st[l]]};return;}
  int mid=l+r>>1;
  build(ls,l,mid);
  build(rs,mid+1,r);
  pushup(k);
}
void update(int k,int l,int r,int x){
  /*{
      cnt++;
  }*/
  if(l==r){tr[k]=(data){val(a[st[l]]),b[st[l]]};return;}
  int mid=l+r>>1;
  if(x<=mid)update(ls,l,mid,x);
  else update(rs,mid+1,r,x);
  pushup(k);
}
data query(int k,int l,int r,int x,int y){
  /*{
      cnt++;
  }*/
  if(l==x&&r==y)return tr[k];
  int mid=l+r>>1;
  if(y<=mid)return query(ls,l,mid,x,y);
  else if(x>mid)return query(rs,mid+1,r,x,y);
  else return query(ls,l,mid,x,mid)+query(rs,mid+1,r,mid+1,y);
}
il void Update_mn(int u){
  int tmp,tu,du,v;
  a[u]=mk(0,0),b[u]=1;
  while(1){
      tot++;
      tu=tp[u];du=dn[u];
      update(1,1,n,id[u]);
      tmp=g[tu],g[tu]=query(1,1,n,id[tu],id[du]).b;
      v=tu,u=fa[tu];
      if(!col[u])break;
      if(dep[u]&1){
          a[u]=a[u]-tmp+g[v];
          b[u]=0;
      }else {
          a[u]=a[u]-(lf[v]-tmp+mod)%mod+(lf[v]-g[v]+mod)%mod;
          b[u]=(lf[u]-(ll)lf[sn[u]]*val(a[u])%mod+mod)%mod;
      }
  }
  now=(ll)now*pw(tmp,mod-2)%mod*g[v]%mod;
}
il void Update_mx(int u){
  int tmp,tu,du,v;
  a[u]=mk(0,0),b[u]=1;
  while(1){
      tot++;
      tu=tp[u];du=dn[u];
      update(1,1,n,id[u]);
      tmp=g[tu],g[tu]=query(1,1,n,id[tu],id[du]).b;
      v=tu,u=fa[tu];
      if(!col[u])break;
      if(dep[u]&1){
          a[u]=a[u]-(lf[v]-tmp+mod)%mod+(lf[v]-g[v]+mod)%mod;
          b[u]=(lf[u]-(ll)lf[sn[u]]*val(a[u])%mod+mod)%mod;
      }else{
          a[u]=a[u]-tmp+g[v];
          b[u]=0;
      }
  }
  now=(ll)now*pw(tmp,mod-2)%mod*g[v]%mod;
}
char ps[1000000],*pp=ps;
void push(char x){
  if(pp==ps+1000000)fwrite(ps,1,1000000,stdout),pp=ps;
  *pp++=x;
}
void write(int x){
  if(!x){push('0');push(' ');return;}
  static int sta[20],top;
  while(x)sta[++top]=x%10,x/=10;
  while(top)push(sta[top--]^'0');
  push(' ');
}
void flush(){fwrite(ps,1,pp-ps,stdout);}
int main(){
  //freopen("minimax.in","r",stdin);
  //freopen("minimax.out","w",stdout);
  n=rd();L=rd();R=rd();
  for(rg int i=1;i<n;++i)adde(rd(),rd());
  dfs_pre(1,0);
  now=1;dfs_key(1);
  ans[1]=(lf[1]-now+mod)%mod;
  build(1,1,n);
  //cerr<<fixed<<setprecision(2)<<1.0*clock()/CLOCKS_PER_SEC<<endl;
  for(rg int i=2,j1=f[1]-1,j2=f[1]+1;i<n;++i){
      while(j1>=1&&j1+i>f[1]){if(d[j1]==1&&col[j1]==1)Update_mn(j1);j1--;}
      while(j2<=n&&j2-i<f[1]){if(d[j2]==1&&col[j2]==2)Update_mx(j2);j2++;}
      ans[i]=(lf[1]-now+mod)%mod;
      /*if(i==1000){
          write(cnt);
          write(tot);
          break;
      }*/
  //  cerr<<fixed<<setprecision(2)<<1.0*clock()/CLOCKS_PER_SEC<<endl;
  }
  ans[n]=lf[1]-1;
  for(rg int i=n;i;--i)ans[i]=(ans[i]-ans[i-1]+mod)%mod;
  for(rg int i=L;i<=R;++i)write(ans[i]);//printf("%d ",ans[i]);
  flush();
  //printf("%.2lf\n",1.0*clock()/CLOCKS_PER_SEC);
  //cerr<<fixed<<setprecision(2)<<1.0*clock()/CLOCKS_PER_SEC<<endl;
  return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄