URAL1553?維護一棵樹，隨時修改某個節(jié)點的權值，詢問（x,y）路徑上權值最大的點。

樹是靜態(tài)的，不過套動態(tài)樹也能過，時限卡的嚴就得上樹鏈剖分了。

還是那句話 splay的核心是splay(x) LCT的核心是access(x)

把SPOJ OTOCI的代碼改了兩行就過了

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm>using namespace std;const int MaxNode=131000;int Lch[MaxNode]; int Rch[MaxNode]; int Pnt[MaxNode]; int Data[MaxNode]; int Sum[MaxNode]; int Rev[MaxNode]; int List[MaxNode]; int maxv[MaxNode]; int Total;inline bool isRoot(int t){return (!Pnt[t]||(Lch[Pnt[t]]!=t&&Rch[Pnt[t]]!=t)); } inline void Update(int cur){maxv[cur]=Data[cur];if(Lch[cur]!=0)maxv[cur]=max(maxv[cur],maxv[Lch[cur]]);if(Rch[cur]!=0)maxv[cur]=max(maxv[cur],maxv[Rch[cur]]); } void Reverse(int cur){if (!Rev[cur]) return;swap(Lch[cur],Rch[cur]);Rev[Lch[cur]]^=1;Rev[Rch[cur]]^=1;Rev[cur]=0; } void LeftRotate(int cur){if (isRoot(cur)) return;int pnt=Pnt[cur],anc=Pnt[pnt];Lch[pnt]=Rch[cur];if (Rch[cur]) Pnt[Rch[cur]]=pnt;Rch[cur]=pnt;Pnt[pnt]=cur;Pnt[cur]=anc;if (anc){if (Lch[anc]==pnt) Lch[anc]=cur;else if (Rch[anc]==pnt) Rch[anc]=cur;}Update(pnt);Update(cur); } void RightRotate(int cur){if (isRoot(cur)) return;int pnt=Pnt[cur],anc=Pnt[pnt];Rch[pnt]=Lch[cur];if (Lch[cur]) Pnt[Lch[cur]]=pnt;Lch[cur]=pnt;Pnt[pnt]=cur;Pnt[cur]=anc;if (anc){if (Rch[anc]==pnt) Rch[anc]=cur;else if (Lch[anc]==pnt) Lch[anc]=cur;}Update(pnt);Update(cur); } void Splay(int cur){int pnt,anc;List[++Total]=cur;for (int i=cur;!isRoot(i);i=Pnt[i]) List[++Total]=Pnt[i];for (;Total;--Total)if (Rev[List[Total]]) Reverse(List[Total]);while (!isRoot(cur)){pnt=Pnt[cur];if (isRoot(pnt)){// 父親是根結點，做一次旋轉if (Lch[pnt]==cur) LeftRotate(cur);else RightRotate(cur);}else{anc=Pnt[pnt];if (Lch[anc]==pnt){if (Lch[pnt]==cur) LeftRotate(pnt),LeftRotate(cur);// 一條線else RightRotate(cur),LeftRotate(cur);// 相反兩次}else{if (Rch[pnt]==cur) RightRotate(pnt),RightRotate(cur);// 一條線else LeftRotate(cur),RightRotate(cur);// 相反兩次}}} } int Expose(int u){int v=0;for (;u;u=Pnt[u]) Splay(u),Rch[u]=v,v=u,Update(u);for (;Lch[v];v=Lch[v]);return v; } void Modify(int x,int d){Splay(x);Data[x]=d;Update(x); } int Query(int x,int y){int rx=Expose(x),ry=Expose(y);if (rx==ry){for (int u=x,v=0;u;u=Pnt[u]){Splay(u);if (!Pnt[u]) return max(max(maxv[Rch[u]],Data[u]),maxv[v]);Rch[u]=v;Update(u);v=u;}}return -1; } bool Join(int x,int y){int rx=Expose(x),ry=Expose(y);if (rx==ry) return false;else{Splay(x);Rch[x]=0;Rev[x]=1;Pnt[x]=y;Update(x);return true;} } void Cut(int x){if (Pnt[x]){Expose(x);Pnt[Lch[x]]=0;Lch[x]=0;Update(x);} } int n,Q;void init(){Total=0;memset(Rev,0,sizeof(Rev));memset(Pnt,0,sizeof(Pnt));memset(Lch,0,sizeof(Lch));memset(Rch,0,sizeof(Rch));memset(Sum,0,sizeof(Sum));memset(Data,0,sizeof(Data));memset(maxv,0,sizeof(maxv)); } char cmd[22]; int main() { freopen("t.txt","r",stdin);init();scanf("%d",&n);for(int i=0;i<n-1;i++){int a,b;scanf("%d%d",&a,&b);Join(a,b);}scanf("%d",&Q);while (Q--){int x,y;scanf("%s%d%d",cmd,&x,&y);if (cmd[0]=='I'){Modify(x,Data[x]+y);}if (cmd[0]=='G'){printf("%d",Query(x,y));if(Q>0)printf("\n");}}return 0; }

　　

轉載于:https://www.cnblogs.com/heisenberg-/p/6597097.html

總結

以上是生活随笔為你收集整理的URAL1553 Caves and Tunnels 树链剖分 动态树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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