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

谁践踏了优雅 2021-09-29 17:46 332阅读 0赞

[传送门][Link 1]

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

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

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

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

然而必然会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 }

转载于:https://www.cnblogs.com/bztMinamoto/p/9398077.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=3531