完了今天才知道原来线段树的动态开点和主席树是不一样的啊

我们先考虑没有宗教信仰的限制，那么就是一个很明显的树剖+线段树，路径查询最大值以及路径和

然后有了宗教信仰的限制该怎么做呢？

先考虑暴力，对每一个信仰建一棵线段树

然而必然会MLE

于是我们只能动态开点

说一下我自己的理解吧，动态开点就是把那些建树过程中没有用的节点删去，以此来节省空间

比如当$sum[p]=0$时，直接删去点$p$

具体实现还是参考一下代码吧

1 // luogu-judger-enable-o2  2 //minamoto  3 #include
     
        4 #define N 300005  5 using namespace std;  6 template
      
       inline bool cmax(T&a,const T&b){
   return a
       
        sz[son[u]]) son[u]=v; 35     } 36 } 37 void dfs2(int u){ 38     if(!top[u]) top[u]=u; 39     dfn[u]=++num,rk[num]=u; 40     if(!son[u]) return; 41     top[son[u]]=top[u],dfs2(son[u]); 42     for(int i=head[u];i;i=Next[i]){ 43         int v=ver[i]; 44         if(v!=fa[u]&&v!=son[u]) dfs2(v); 45     } 46 } 47 void update(int p){ 48     mx[p]=max(mx[L[p]],mx[R[p]]); 49     sum[p]=sum[L[p]]+sum[R[p]]; 50 } 51 void modify(int &p,int l,int r,int k,int v){ 52     if(!p) p=++cnt; 53     if(l>=r){ 54         mx[p]=sum[p]=v;return; 55     } 56     int mid=(l+r)>>1; 57     if(k<=mid) modify(L[p],l,mid,k,v); 58     else modify(R[p],mid+1,r,k,v); 59     update(p); 60     if(sum[p]==0) p=0; 61 } 62 int askmax(int p,int l,int r,int ql,int qr){ 63     if(!p) return -1; 64     if(ql<=l&&qr>=r) return mx[p]; 65     int mid=(l+r)>>1,val=-1; 66     if(ql<=mid) cmax(val,askmax(L[p],l,mid,ql,qr)); 67     if(qr>mid) cmax(val,askmax(R[p],mid+1,r,ql,qr)); 68     return val; 69 } 70 int asksum(int p,int l,int r,int ql,int qr){ 71     if(!p) return 0; 72     if(ql<=l&&qr>=r) return sum[p]; 73     int mid=(l+r)>>1,val=0; 74     if(ql<=mid) val+=asksum(L[p],l,mid,ql,qr); 75     if(qr>mid) val+=asksum(R[p],mid+1,r,ql,qr); 76     return val; 77 } 78 int path_max(int u,int v){ 79     int ans=-1; 80     int xz=yc[u]; 81     while(top[u]!=top[v]){ 82         if(d[top[u]]