用 set 維護子樹信息，細節較多。

Code:

#include <cstring> #include <cstdio> #include <algorithm> #include <set> #include <string> #define setIO(s) freopen(s".in","r",stdin), freopen(s".out","w",stdout) #define maxn 100009 #define inf -2147483647 using namespace std; int fat[maxn]; int n,m; struct Graph{int head[maxn],to[maxn<<1],nex[maxn<<1],cnt; void addedge(int u,int v){ nex[++cnt]=head[u],head[u]=cnt,to[cnt]=v; } void dfs(int u,int father){fat[u]=father;for(int v=head[u];v;v=nex[v]) if(to[v]!=father) dfs(to[v],u);}void Build(){for(int i=1;i<n;++i){int a,b;scanf("%d%d",&a,&b), addedge(a,b),addedge(b,a); }dfs(1,0);} }G; int col[maxn],v[maxn]; struct LCT{multiset<int>s[maxn]; multiset<int>::reverse_iterator rit;int ch[maxn][2],f[maxn];int siz[maxn],mx[maxn]; void init(){ mx[0]=-2147483647; } int value(int x) { rit=s[x].rbegin(); return (*rit); }int get(int x){ return ch[f[x]][1]==x; }int lson(int x){ return ch[x][0];}int rson(int x){ return ch[x][1];}int isRoot(int x){ return !(ch[f[x]][0]==x||ch[f[x]][1]==x); }void pushup(int x){ if(!x) return; mx[x]=max(v[x],max(mx[lson(x)],mx[rson(x)])); if(!s[x].empty()) mx[x]=max(mx[x],value(x)); }void rotate(int x){int old=f[x],oldf=f[old],which=get(x);if(!isRoot(old)) ch[oldf][ch[oldf][1]==old]=x; ch[old][which]=ch[x][which^1],f[ch[old][which]]=old;ch[x][which^1]=old,f[old]=x,f[x]=oldf;pushup(old),pushup(x);}void splay(int x){int u=x;while(!isRoot(u)) u=f[u];u=f[u];for(int fa;(fa=f[x])!=u;rotate(x)) if(f[fa]!=u) rotate(get(fa)==get(x)?fa:x);}void Access(int x){for(int y=0;x;y=x,x=f[x]){splay(x);if(rson(x)) s[x].insert(mx[rson(x)]); if(ch[x][1]=y) s[x].erase(s[x].find(mx[y])) ; pushup(x);}}void cut(int a,int b){ if(!a) return; Access(b),splay(b),ch[b][0]=f[ch[b][0]]=0,pushup(b);}void link(int a,int b){ if(!a) return; Access(a),splay(a),Access(b),splay(b);f[b]=a,ch[a][1]=b,pushup(a);}int findRoot(int a){Access(a),splay(a);while(ch[a][0]) a=ch[a][0];return a;} }tree[2]; int main(){//setIO("debug");scanf("%d",&n),G.Build(),tree[0].init(),tree[1].init();for(int i=1;i<=n;++i) scanf("%d",&col[i]); for(int i=1;i<=n;++i) scanf("%d",&v[i]); fat[1]=n+1,v[n+1]=tree[1].mx[n+1]=tree[0].mx[n+1]=inf; for(int i=1;i<=n;++i) tree[col[i]].link(fat[i],i); int opt,a;scanf("%d",&m);for(int i=1;i<=m;++i){scanf("%d%d",&opt,&a);if(opt==0) {int x=tree[col[a]].findRoot(a);tree[col[a]].splay(x); if(col[x]==col[a]) printf("%d\n",tree[col[a]].mx[x]);else printf("%d\n",tree[col[a]].mx[tree[col[a]].ch[x][1]]); }if(opt==1) {tree[col[a]].cut(fat[a],a),col[a]^=1,tree[col[a]].link(fat[a],a);}if(opt==2){tree[col[a]].Access(a),tree[col[a]].splay(a);scanf("%d",&v[a]); tree[col[a]].pushup(a); } }return 0; }

　　

轉載于:https://www.cnblogs.com/guangheli/p/10159842.html

總結

以上是生活随笔為你收集整理的BZOJ 3639: Query on a tree VII LCT_set维护子树信息的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。