分类讨论好题（也不太算分类讨论）

方法：感受过程手玩，考虑能不能提前预算一些东西，或者递推，递归

也就是，找问题划分点

 

关注一个点x到根节点的最大值mx[x]（包括自己）

因为最大值的父亲fa[mx[x]]的ans一定不会扩展mx[x]

所以求出mx[x]

对于mx[x]!=x情况

定义son[x]，x的mx[x]往x方向走的第一个儿子

x一定会历经艰难扩展到mx，期间son[x]子树内，mx[*]=mx[x]的*都会被扩展。第一部分

走到了mx

之后，son[x]子树不会有任何扩展，

但是还可能会扩展一些mx除了son[x]的其他子树点y

如果y到根的次大值（最大值一定也是mx）是mx到根的次大值se[mx]的话，那么一定在次大值及之前会被扩展。第二部分

所以，次大值也关心。

然后就是ans[fa[mx]]了，之前已经算过，而且不会算重！第三部分

 

子树某个值出现次数

第一部分线段树合并

第二部分线段树合并，再减去son[x]子树的贡献

 

对于mx[x]==x情况

更好处理

直接变成上述情况的第二部分。mx子树内，se[*]=se[x]的个数

线段树合并。

 

代码：

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=998244353;int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y;}void inc(int &x,int y){x=ad(x,y);}int mul(int x,int y){ return (ll)x*y%mod;}void inc2(int &x,int y){x=mul(x,y);}int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}}//using namespace Modulo;namespace Miracle{const int N=2e5+5;int n;struct node{ int nxt,to;}e[2*N];int hd[N],cnt;void add(int x,int y){ e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt;}int se[N],mx[N];int son[N];int pa[N];void dfs(int x,int fa){ se[x]=se[fa]; mx[x]=mx[fa]; if(x>mx[x]){ se[x]=mx[x];mx[x]=x; }else se[x]=max(se[x],x); if(mx[x]==mx[fa]){ if(mx[fa]==fa) son[x]=x; else son[x]=son[fa]; } for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; pa[y]=x; dfs(y,x); }}struct tr{ int ls,rs; int cnt[2];}t[N*60];int tot;int rt[N];#define mid ((l+r)>>1)void upda(int &x,int l,int r,int p,int c){ if(!x) x=++tot; if(l==r){ t[x].cnt[c]++;return; } if(p<=mid) upda(t[x].ls,l,mid,p,c); else upda(t[x].rs,mid+1,r,p,c);}int merge(int x,int y,int l,int r){ if(!x||!y) return x+y; if(l==r){ t[x].cnt[0]=t[x].cnt[0]+t[y].cnt[0]; t[x].cnt[1]=t[x].cnt[1]+t[y].cnt[1]; return x; } t[x].ls=merge(t[x].ls,t[y].ls,l,mid); t[x].rs=merge(t[x].rs,t[y].rs,mid+1,r); return x;}void dfs2(int x,int fa){ upda(rt[x],1,n,mx[x],1); upda(rt[x],1,n,se[x],0); for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; dfs2(y,x); rt[x]=merge(rt[x],rt[y],1,n); }}int query(int x,int l,int r,int p,int c){ if(!x) return 0; if(l==r) return t[x].cnt[c]; if(p<=mid) return query(t[x].ls,l,mid,p,c); else return query(t[x].rs,mid+1,r,p,c);}int ans[N];void fin(int x,int fa){ if(x!=1){ if(mx[x]!=x){ int A=query(rt[son[x]],1,n,mx[x],1),B=query(rt[mx[x]],1,n,se[mx[x]],0),C=-query(rt[son[x]],1,n,se[mx[x]],0),D=ans[pa[mx[x]]]; // cout<<" xx "<
           
            <<" : "<
            <<" "<<<" "<
              
               <<" "<
               
                <
               
              
           
          
         
        
       
      
     

 mx的发现很关键，以mx位置为划分点，可以把问题分成若干部分处理，

由于fa[mx]不会再进入mx，还支持递归！