[SDOI2014]旅行

題意：

n個(gè)城市，n-1條邊，任意兩個(gè)城市互通，每個(gè)城市有所信奉的宗教和城市評(píng)級(jí)，有四種指令：
1.將城市x的居民改信為c教
2.將城市x的評(píng)級(jí)調(diào)整為w
3.統(tǒng)計(jì)x到y(tǒng)，路上所有的城市的評(píng)級(jí)綜合（被記錄的城市宗教必須與x和y相同，數(shù)據(jù)保證x和y宗教一致）
4.統(tǒng)計(jì)x到y(tǒng)，路上的評(píng)級(jí)最大值（被記錄的城市要求與上述一樣）
按照要求輸出答案

題解：

參考文章為洛谷題解的第一篇（文章好像顯示不可查看
洛谷的題解第一頁(yè)
題目比較麻煩，因?yàn)橛袃蓚€(gè)要維護(hù)的量，如果是一個(gè)還好說(shuō)，對(duì)于樹(shù)上維護(hù)那肯定是樹(shù)鏈剖分，現(xiàn)在關(guān)鍵就是如果確保只統(tǒng)計(jì)同一宗教的評(píng)級(jí)
我們可以將每個(gè)宗教建立一個(gè)線段樹(shù)這樣分開(kāi)維護(hù)不久ok了，但是內(nèi)存會(huì)超，那我們就主席樹(shù)，動(dòng)態(tài)開(kāi)點(diǎn)
現(xiàn)在講講具體細(xì)節(jié)：
動(dòng)態(tài)開(kāi)點(diǎn)就不說(shuō)了
我們講講改信其他教和評(píng)級(jí)調(diào)整如何實(shí)現(xiàn)？
原本是a教，改成c教
那我們就先到a教的線段樹(shù)中找到這個(gè)點(diǎn)，然后將其評(píng)級(jí)和評(píng)級(jí)最大值都清零（可以理解為刪除這個(gè)點(diǎn)，但實(shí)際還存在只是沒(méi)有值），然后到c教里將這個(gè)點(diǎn)再加上，并加上評(píng)級(jí)
注意：在刪除過(guò)程中記得要pushup(root)，你刪除一個(gè)點(diǎn)后，整個(gè)數(shù)的最大值和權(quán)值和發(fā)生了改變，所以即可更新到根節(jié)點(diǎn)
評(píng)級(jí)更新也是差不多，先把原本評(píng)級(jí)刪去，再附上新評(píng)級(jí)
剩下都是樹(shù)鏈剖分常規(guī)操作
代碼有詳細(xì)注釋

代碼：

#include<bits/stdc++.h> using namespace std; struct node{int to,next; }g[1000000]; int tot,n,m,cnt,w[100004],zj[100004],len,head[100004],dep[100004],wson[100004],top[100004],tpos[100004],pre[100004],fa[100004],size[100004]; inline void made(int from,int to){g[++tot].to=to;g[tot].next=head[from];head[from]=tot; } inline void dfs1(int rt,int ff){fa[rt]=ff;dep[rt]=dep[ff]+1;size[rt]=1;for (int i=head[rt];i;i=g[i].next){int v=g[i].to;if (v==ff) continue;dfs1(v,rt);size[rt]+=size[v];if (!wson[rt]||size[wson[rt]]<size[v]) wson[rt]=v;} } inline void dfs2(int rt,int tops){tpos[rt]=++cnt;pre[cnt]=rt;top[rt]=tops;if (wson[rt]) dfs2(wson[rt],tops);for (int i=head[rt];i;i=g[i].next){int v=g[i].to;if (v==fa[rt]||v==wson[rt]) continue;dfs2(v,v);} } int root[100004]; struct Node{int l,r,max,tot; }tree[20000110]; inline void update(int &rt,int w,int l,int r,int pos){//加點(diǎn)操作 if (!rt) rt=++len;//動(dòng)態(tài)開(kāi)點(diǎn) tree[rt].max=max(tree[rt].max,w);tree[rt].tot+=w;if (l==r) return;int mid=(l+r)/2;if (mid>=pos) update(tree[rt].l,w,l,mid,pos);else update(tree[rt].r,w,mid+1,r,pos); } inline void remove(int &rt,int l,int r,int pos){//刪點(diǎn)操作 if (l==r){ tree[rt].tot=0;tree[rt].max=0;return; }int mid=(l+r)/2;if (mid>=pos) remove(tree[rt].l,l,mid,pos);else remove(tree[rt].r,mid+1,r,pos);tree[rt].tot=tree[tree[rt].l].tot+tree[tree[rt].r].tot;tree[rt].max=max(tree[tree[rt].l].max,tree[tree[rt].r].max); }inline int querytot(int rt,int lb,int rb,int l,int r){//查詢(xún)區(qū)間總值 if (r<lb||l>rb) return 0;if (r>=rb&&l<=lb) return tree[rt].tot;int mid=(lb+rb)/2;return querytot(tree[rt].l,lb,mid,l,r)+querytot(tree[rt].r,mid+1,rb,l,r); } inline int querymax(int rt,int lb,int rb,int l,int r){//查詢(xún)區(qū)間最大值 if (r<lb||l>rb) return 0;if (r>=rb&&l<=lb) return tree[rt].max;int mid=(lb+rb)/2;return max(querymax(tree[rt].l,lb,mid,l,r),querymax(tree[rt].r,mid+1,rb,l,r)); } //--上面為動(dòng)態(tài)開(kāi)點(diǎn)線段樹(shù)，下面為樹(shù)鏈剖分 inline int sigmax(int u,int v,int zj){int ans=0;while (top[u]!=top[v]){if (dep[top[u]]<dep[top[v]]) swap(u,v);ans=max(ans,querymax(root[zj],1,n,tpos[top[u]],tpos[u]));u=fa[top[u]];}if (dep[u]<dep[v]) swap(u,v);ans=max(ans,querymax(root[zj],1,n,tpos[v],tpos[u]));return ans; } inline int sigtot(int u,int v,int zj){int ans=0;while (top[u]!=top[v]){if (dep[top[u]]<dep[top[v]]) swap(u,v);ans=ans+querytot(root[zj],1,n,tpos[top[u]],tpos[u]);u=fa[top[u]];}if (dep[u]<dep[v]) swap(u,v);ans=ans+querytot(root[zj],1,n,tpos[v],tpos[u]);return ans; } char s[100]; int main(){len=0;scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%d%d",&w[i],&zj[i]);}int x,y;for (int i=1;i<n;i++){scanf("%d%d",&x,&y);made(x,y);made(y,x);}dfs1(1,0);dfs2(1,1);for (int i=1;i<=n;i++){update(root[zj[i]],w[i],1,n,tpos[i]);} while (m--){scanf("%s",s);scanf("%d%d",&x,&y);switch (s[1]){case 'C':{//改信了c教 remove(root[zj[x]],1,n,tpos[x]);zj[x]=y;update(root[zj[x]],w[x],1,n,tpos[x]);break;}case 'W':{//城市x的評(píng)級(jí)調(diào)整為w;remove(root[zj[x]],1,n,tpos[x]);w[x]=y;update(root[zj[x]],w[x],1,n,tpos[x]);break;}case 'S':{//記錄評(píng)級(jí)總和 printf("%d\n",sigtot(x,y,zj[x]));break;} case 'M':{//記錄評(píng)級(jí)最大值 printf("%d\n",sigmax(x,y,zj[x]));break;}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[SDOI2014]旅行的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。