【算法竞赛学习笔记】[SDOI2011]染色（路径染色+色段查询） |
您所在的位置：网站首页 › sacai染色 › 【算法竞赛学习笔记】[SDOI2011]染色（路径染色+色段查询） |
|
title : [SDOI2011]染色（路径染色+色段查询） tags : ACM,数据结构 date : 2021-11-16 author : Linno P2486 [SDOI2011]染色 题面给一棵树，支持两种操作： ①给定u,v,w，将u到v的路径上所有节点染成颜色w。 ②给定u,v，查询u到v路径上颜色段的数量。 树链剖分+线段树树链剖分将无根树拍平后，用线段树去做。维护每个区间的左颜色、右颜色、色段和以及tag，如果合并的时候两端颜色一致，那么ans-1。 #include using namespace std; const int N=1e5+7; int n,m,col[N]; vectorG[N]; void addedge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } int sz[N],dep[N],son[N],fa[N],bel[N],dfn[N],idfn[N],idx=0; inline void dfs1(int x){ sz[x]=1; for(int i=0;in>>m; for(int i=1;i>col[i]; for(int i=1;i>u>>v; addedge(u,v); } dfs1(1); dfs2(1,1); build(1,1,n); for(int i=1;i>op; if(op=='Q'){ cin>>u>>v; //路径查询 int res=0,Cson,Cfa; while(bel[u]!=bel[v]){ if(dep[bel[u]]w; //路径涂色 while(bel[u]!=bel[v]){ if(dep[bel[u]] |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |