BZOJ3531-[Sdoi2014]旅行（树剖+线段树动态开点）-蒲公英云

BZOJ3531-[Sdoi2014]旅行（树剖+线段树动态开点）

传送门

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

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

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

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

然而必然会MLE

于是我们只能动态开点

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

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

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

1 // luogu-judger-enable-o2
  2 //minamoto
  3 #include<bits/stdc++.h>
  4 #define N 300005
  5 using namespace std;
  6 template<class T>inline bool cmax(T&a,const T&b){
    return a<b?a=b,1:0;}
  7 inline int read(){
  8     #define num ch-'0'
  9     char ch;bool flag=0;int res;
 10     while(!isdigit(ch=getchar()))
 11     (ch=='-')&&(flag=true);
 12     for(res=num;isdigit(ch=getchar());res=res*10+num);
 13     (flag)&&(res=-res);
 14     #undef num
 15     return res;
 16 }
 17 int L[N<<2],R[N<<2],mx[N<<2],sum[N<<2];
 18 int sz[N],fa[N],son[N],dfn[N],rk[N],d[N],top[N],val[N],c[N];
 19 int ver[N<<1],head[N],Next[N<<1],yval[N],yc[N];
 20 int rt[N];
 21 int n,m,num,tot,cnt;
 22 inline void add(int u,int v){
 23     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
 24     ver[++tot]=u,Next[tot]=head[v],head[v]=tot;
 25 }
 26 void dfs1(int u){
 27     sz[u]=1,d[u]=d[fa[u]]+1;
 28     for(int i=head[u];i;i=Next[i]){
 29         if(ver[i]==fa[u]) continue;
 30         int v=ver[i];
 31         fa[v]=u;
 32         dfs1(v);
 33         sz[u]+=sz[v];
 34         if(!son[u]||sz[v]>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]]<d[top[v]]) swap(u,v);
 83         cmax(ans,askmax(rt[xz],1,num,dfn[top[u]],dfn[u]));
 84         u=fa[top[u]];
 85     }
 86     if(d[u]<d[v]) swap(u,v);
 87     cmax(ans,askmax(rt[xz],1,num,dfn[v],dfn[u]));
 88     return ans;
 89 }
 90 int path_sum(int u,int v){
 91     int ans=0;
 92     int xz=yc[u];
 93     while(top[u]!=top[v]){
 94         if(d[top[u]]<d[top[v]]) swap(u,v);
 95         ans+=asksum(rt[xz],1,num,dfn[top[u]],dfn[u]);
 96         u=fa[top[u]];
 97     }
 98     if(d[u]<d[v]) swap(u,v);
 99     ans+=asksum(rt[xz],1,num,dfn[v],dfn[u]);
100     return ans;
101 }
102 int main(){
103     //freopen("testdata.in","r",stdin);
104     int n,q;
105     n=read(),q=read();
106     for(int i=1;i<=n;++i)
107     yval[i]=read(),yc[i]=read();
108     for(int i=1;i<n;++i){
109         int u=read(),v=read();
110         add(u,v);
111     }
112     dfs1(1),dfs2(1);
113     for(int i=1;i<=n;++i)
114     modify(rt[yc[rk[i]]],1,num,i,yval[rk[i]]);
115     while(q--){
116         char s[10];int x,y;
117         scanf("%s",s);
118         x=read(),y=read();
119         switch(s[1]){
120             case 'C':{
121                 modify(rt[yc[x]],1,num,dfn[x],0);
122                 yc[x]=y;
123                 modify(rt[yc[x]],1,num,dfn[x],yval[x]);
124                 break;
125             }
126             case 'W':{
127                 yval[x]=y;
128                 modify(rt[yc[x]],1,num,dfn[x],yval[x]);
129                 break;
130             }
131             case 'S':{
132                 printf("%d\n",path_sum(x,y));
133                 break;
134             }
135             case 'M':{
136                 printf("%d\n",path_max(x,y));
137                 break;
138             }
139         }
140     }
141     return 0;
142 }