[bzoj3531]旅行

迷南。 2021-11-17 15:36 235阅读 0赞

对其树剖，然后对于同一种宗教开一棵动态开点的区间线段树，维护区间max和sum，像普通的树剖一样处理即可。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define N 100005
     4 #define mid (l+r>>1)
     5 struct ji{
     6     int nex,to;
     7 }edge[N<<1];
     8 int E,V,n,m,x,y,r[N],w[N],c[N],head[N],fa[N],sh[N],sz[N],ma[N],top[N],id[N],ls[N*40],rs[N*40],f[N*40][2];
     9 char s[11];
    10 void add(int x,int y){
    11     edge[E].nex=head[x];
    12     edge[E].to=y;
    13     head[x]=E++;
    14 }
    15 int up(int x,int y,int p){
    16     if (p)return x+y;
    17     return max(x,y);
    18 }
    19 void update(int &k,int l,int r,int x,int y){
    20     if (!k)k=++V;
    21     if (l==r){
    22         f[k][0]=f[k][1]=y;
    23         return;
    24     }
    25     if (x<=mid)update(ls[k],l,mid,x,y);
    26     else update(rs[k],mid+1,r,x,y);
    27     for(int i=0;i<2;i++)f[k][i]=up(f[ls[k]][i],f[rs[k]][i],i);
    28 }
    29 int query(int k,int l,int r,int x,int y,int p){
    30     if ((x>r)||(l>y)||(!k))return 0;
    31     if ((x<=l)&&(r<=y))return f[k][p];
    32     return up(query(ls[k],l,mid,x,y,p),query(rs[k],mid+1,r,x,y,p),p);
    33 }
    34 void dfs(int k,int f,int s){
    35     fa[k]=f;
    36     sh[k]=s;
    37     sz[k]=1; 
    38     for(int i=head[k];i!=-1;i=edge[i].nex)
    39         if (edge[i].to!=f){
    40             dfs(edge[i].to,k,s+1);
    41             sz[k]+=sz[edge[i].to];
    42             if (sz[ma[k]]<sz[edge[i].to])ma[k]=edge[i].to;
    43         }
    44 }
    45 void dfs2(int k,int t){
    46     id[k]=++x;
    47     update(r[c[k]],1,N-5,x,w[k]);
    48     top[k]=t;
    49     if (ma[k])dfs2(ma[k],t);
    50     for(int i=head[k];i!=-1;i=edge[i].nex)
    51         if ((edge[i].to!=fa[k])&&(edge[i].to!=ma[k]))dfs2(edge[i].to,edge[i].to);
    52 }
    53 int calc(int k,int x,int y,int p){
    54     int ans=0;
    55     while (top[x]!=top[y]){
    56         if (sh[top[x]]<sh[top[y]])swap(x,y);
    57         ans=up(ans,query(k,1,N-5,id[top[x]],id[x],p),p);
    58         x=fa[top[x]];
    59     }
    60     if (sh[x]>sh[y])swap(x,y);
    61     return up(ans,query(k,1,N-5,id[x],id[y],p),p);
    62 }
    63 int main(){
    64     scanf("%d%d",&n,&m);
    65     memset(head,-1,sizeof(head));
    66     for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]);
    67     for(int i=1;i<n;i++){
    68         scanf("%d%d",&x,&y);
    69         add(x,y);
    70         add(y,x);
    71     }
    72     dfs(1,1,0);
    73     x=0;
    74     dfs2(1,1);
    75     for(int i=1;i<=m;i++){
    76         scanf("%s%d%d",s,&x,&y);
    77         if (s[0]=='Q'){
    78             printf("%d\n",calc(r[c[x]],x,y,s[1]=='S'));
    79             continue;
    80         }
    81         if (s[1]=='W')w[x]=y;
    82         else{
    83             update(r[c[x]],1,N-5,id[x],0);
    84             c[x]=y;
    85         }
    86         update(r[c[x]],1,N-5,id[x],w[x]);
    87     }
    88 }

转载于:https://www.cnblogs.com/PYWBKTDA/p/11249813.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/420ba8abb6e94ca9ac42f4fb3a2e694a.png