首页 > 代码库 > BZOJ 3639: Query on a tree VII
BZOJ 3639: Query on a tree VII
Description
一棵树,支持三种操作,修改点权,修改颜色,问所有与他路径上颜色相同的点的最大权,包含这两个点.
Sol
LCT.
用LCT来维护重边,对于每个节点在建一个set用来维护轻边,这样Link和Cut是时候就非常好操作了,直接Access一下,Splay一下,直接删掉就可以了.
因为set是不统计重边的,然后对于每个节点的信息由他的父亲来保存,因为一个节点可能有很多儿子但一定只有一个父亲.
还有一个问题就是每个点的权值不能建全局的,因为维护的两颗LCT不能够同时删除,所以每个LCT都要有个点权的数组.
Code
/************************************************************** Problem: 3639 User: BeiYu Language: C++ Result: Accepted Time:4060 ms Memory:16276 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; #define debug(a) cout<<#a<<"="<<a<<" "typedef long long LL;const int N = 1e5+50; inline int in(int x=0,char ch=getchar(),int v=1) { while(ch>‘9‘ || ch<‘0‘) v=ch==‘-‘?-1:v,ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x*v; } int n,q;vector < int > g[N];int col[N],F[N]; struct LinkCutTree { int f[N],ch[N][2]; int mx[N],w[N]; multiset< int,greater< int > > s[N]; #define lc(o) ch[o][0] #define rc(o) ch[o][1] int isrt(int o) { return f[o]==0 || (lc(f[o])!=o && rc(f[o])!=o); } void Update(int o) { mx[o]=w[o]; if(!s[o].empty()) mx[o]=max(mx[o],*s[o].begin()); if(lc(o)) mx[o]=max(mx[o],mx[lc(o)]); if(rc(o)) mx[o]=max(mx[o],mx[rc(o)]); } void Rot(int o) { int p=f[o],k=f[p],r=rc(p)==o; if(!isrt(p)) ch[k][rc(k)==p]=o; f[ch[o][r^1]]=p,f[p]=o,f[o]=k; ch[p][r]=ch[o][r^1],ch[o][r^1]=p; Update(p),Update(o); } void Splay(int o) {// cout<<"S"<<endl; for(;!isrt(o);) { int p=f[o],k=f[p]; if(isrt(p)) Rot(o); else if((rc(p)==o)==(rc(k)==p)) Rot(p),Rot(o); else Rot(o),Rot(o); }Update(o); } void Access(int o) {// cout<<"A"<<endl; for(int p=0;o;p=o,o=f[o]) { Splay(o); if(rc(o)) s[o].insert(mx[rc(o)]); if(rc(o)=p,p) s[o].erase(s[o].find(mx[p])); } } void Link(int o) {// cout<<"L"<<endl; Access(F[o]),Splay(F[o]),Splay(o); f[o]=F[o],rc(f[o])=o; } void Cut(int o) {// cout<<"C"<<endl; Access(o),Splay(o),f[lc(o)]=0,lc(o)=0; } void Change(int o,int v) {// cout<<"M"<<endl; Access(o),Splay(o),w[o]=v,Update(o); } int Query(int o) {// cout<<"Q"<<endl; Access(o),Splay(o); int x=o; for(;lc(x);x=lc(x));Splay(x); if(col[x]!=col[o]) return mx[rc(x)]; else return mx[x]; }}py[2]; void AddEdge(int u,int v) { g[u].push_back(v); }void DFS(int u,int fa) { for(int i=0,v;i<(int)g[u].size();i++) if((v=g[u][i])!=fa) { F[v]=u,py[col[v]].f[v]=u; DFS(v,u);// debug(py[col[v]].mx[v])<<endl; py[col[v]].s[u].insert(py[col[v]].mx[v]); }py[0].Update(u),py[1].Update(u);}void init() { n=in(); for(int i=1,u,v;i<n;i++) { u=in(),v=in(),AddEdge(u,v),AddEdge(v,u); } for(int i=1;i<=n;i++) col[i]=in(); for(int i=1;i<=n;i++) py[0].mx[i]=py[0].w[i]=py[1].mx[i]=py[1].w[i]=in(); DFS(1,1);// debug(py[1].mx[1])<<endl;} int main() {// freopen("in.in","r",stdin); init(); for(int q=in();q--;) { int opt=in(),u=in(),v; if(opt==0) printf("%d\n",py[col[u]].Query(u)); else if(opt==1) { if(F[u]) py[col[u]].Cut(u); col[u]^=1; if(F[u]) py[col[u]].Link(u); } else { v=in(); py[0].Change(u,v); py[1].Change(u,v); } } return 0;}
BZOJ 3639: Query on a tree VII
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。