[Luogu 2486] SDOI2011 染色

---

樹剖水題，線段樹維護。

詳細題解不寫了。

我只想說我寫的線段樹又變漂亮了qwq

---

#include <algorithm> #include <cstdio> #include <cstring> const int MAXN=100010; int n,m; class HLD {private:bool vis[MAXN];int num;static int rank[MAXN];static struct Node{int v,depth,father,son,top,size,DFN;}s[MAXN];class SegmentTree{private:struct Node{int v,left,right,lazy,color[2];Node *c[2];Node(int l,int r):left(l),right(r),lazy(0){memset(color,0,sizeof color);c[0]=c[1]=nullptr;if(l==r){v=1;color[0]=color[1]=s[rank[l]].v;return;}int mid=l+r>>1;c[0]=new Node(l,mid);c[1]=new Node(mid+1,r);PushUp();}~Node(void){if(c[0]!=nullptr)delete c[0];if(c[1]!=nullptr)delete c[1];}void Modify(int x){v=1;lazy=color[0]=color[1]=x;}void PushUp(void){v=c[0]->v+c[1]->v;color[0]=c[0]->color[0];color[1]=c[1]->color[1];if(c[0]->color[1]==c[1]->color[0])--v;}void PushDown(void){if(c[0]!=nullptr)c[0]->Modify(lazy);if(c[1]!=nullptr)c[1]->Modify(lazy);lazy=0;}int Color(int x){if(left==right)return color[0];if(lazy)PushDown();int mid=left+right>>1;if(x>mid)return c[1]->Color(x);elsereturn c[0]->Color(x);}void Change(int l,int r,int v){if(l==left && r==right){Modify(v);return;}if(lazy)PushDown();int mid=left+right>>1;if(r<=mid)c[0]->Change(l,r,v);else if(l>mid)c[1]->Change(l,r,v);else{c[0]->Change(l,mid,v);c[1]->Change(mid+1,r,v);}PushUp();}int Query(int l,int r){if(l==left && r==right)return v;int mid=left+right>>1;if(lazy)PushDown();if(r<=mid)return c[0]->Query(l,r);else if(l>mid)return c[1]->Query(l,r);else{int ans=c[0]->Query(l,mid)+c[1]->Query(mid+1,r);if(c[0]->color[1]==c[1]->color[0])--ans;return ans;}}}*root;public:SegmentTree(int n){root=new Node(1,n);}~SegmentTree(void){delete root;}int Color(int x){return root->Color(x);}void Change(int l,int r,int v){root->Change(l,r,v);}int Query(int l,int r){return root->Query(l,r);}}*T;struct Edge{int to;Edge *next;Edge(int to,Edge* next):to(to),next(next){}~Edge(void){if(next!=nullptr)delete next;}}*head[MAXN];void AddEdges(int u,int v){head[u]=new Edge(v,head[u]);head[v]=new Edge(u,head[v]);}void DFS1(int u,int k){s[u].depth=k;s[u].size=1;int v;for(Edge *i=head[u];i!=nullptr;i=i->next)if(!s[v=i->to].size){DFS1(v,k+1);s[v].father=u;s[u].size+=s[v].size;if(s[v].size>s[s[u].son].size)s[u].son=v;}}void DFS2(int u,int top){s[u].top=top;s[u].DFN=++num;rank[num]=u;vis[u]=true;if(s[u].son)DFS2(s[u].son,top);int v;for(Edge *i=head[u];i!=nullptr;i=i->next)if(!vis[v=i->to])DFS2(v,v);}public:HLD(int n):num(0){memset(s,0,sizeof s);std::fill(head+1,head+n+1,nullptr);for(int i=1;i<=n;++i)scanf("%d",&s[i].v);for(int i=1,u,v;i<n;++i){scanf("%d %d",&u,&v);AddEdges(u,v);}DFS1(1,1);DFS2(1,1);T=new SegmentTree(n);}~HLD(void){for(int i=1;i<=n;++i)delete head[i];delete T;}void Change(int x,int y){int a,b,v;scanf("%d",&v);while((a=s[x].top)^(b=s[y].top))if(s[a].depth>s[b].depth){T->Change(s[a].DFN,s[x].DFN,v);x=s[a].father;}else{T->Change(s[b].DFN,s[y].DFN,v);y=s[b].father;}if(s[x].depth<s[y].depth)T->Change(s[x].DFN,s[y].DFN,v);elseT->Change(s[y].DFN,s[x].DFN,v);}void Query(int x,int y){int a,b,ans=0;while((a=s[x].top)^(b=s[y].top))if(s[a].depth>s[b].depth){ans+=T->Query(s[a].DFN,s[x].DFN);x=s[a].father;if(T->Color(s[a].DFN)==T->Color(s[x].DFN))--ans;}else{ans+=T->Query(s[b].DFN,s[y].DFN);y=s[b].father;if(T->Color(s[b].DFN)==T->Color(s[y].DFN))--ans;}ans+=s[x].depth<s[y].depth ? T->Query(s[x].DFN,s[y].DFN) : T->Query(s[y].DFN,s[x].DFN);printf("%d\n",ans);} }*T; int HLD::rank[MAXN]; HLD::Node HLD::s[MAXN]; int main(int argc,char** argv) {scanf("%d %d",&n,&m);T=new HLD(n);char c;for(int i=1,x,y;i<=m;++i){scanf("\n%c %d %d",&c,&x,&y);if(c=='C')T->Change(x,y);elseT->Query(x,y);}delete T;return 0; }

謝謝閱讀。

轉載于:https://www.cnblogs.com/Capella/p/9191205.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[Luogu 2486] SDOI2011 染色的全部內容，希望文章能夠幫你解決所遇到的問題。

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