SPOJ COT2 Count on a tree II (树上莫队)
题目链接:http://www.spoj.com/problems/COT2/
参考博客:http://www.cnblogs.com/xcw0754/p/4763804.html
上面这个人推导部分写的简洁明了,方便理解,但是最后的分情况讨论有些迷,感觉是不必要的,更简洁的思路看下面的博客
传送门:http://blog.csdn.net/kuribohg/article/details/41458639
题意是这样的,给你一棵无根树,给你m个查询,每次查询输出节点x到节点y路径上不同颜色的节点有多少个(包括xy)
没什么说的,直接上代码吧
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int const MAX_N=+;
int const MAX_M=+;
int n,m,ans,nowLca,lastL,lastR,tempAns;
int color[MAX_N];
vector<int> allColor;
vector<int>::iterator it;
int lin[MAX_N],e_cnt;
struct Query{
int x;
int y;
int id;
int ans;
}query[MAX_M];
struct Edge{
int next;
int y;
}e[*MAX_N];
void insert(int u,int v){
e[++e_cnt].next=lin[u];
e[e_cnt].y=v;
lin[u]=e_cnt;
}
int b_len,b_cnt,bk[MAX_N];
int fa[MAX_N][],deep[MAX_N];
int n_cnt,dfn[MAX_N],top,stack[MAX_N];
bool vis[MAX_N];
void dfs(int u){
dfn[u]=++n_cnt;
int btm=top;
for(int i=lin[u];i;i=e[i].next){
int v=e[i].y;
if(!dfn[v]){
fa[v][]=u;
deep[v]=deep[u]+;
dfs(v);
if(top-btm>=b_len){
b_cnt++;
while(top>btm){
bk[stack[top--]]=b_cnt;
}
}
}
}
stack[++top]=u;
}
bool queryCmp_xkb_ydfn(Query a,Query b){
if(bk[a.x]==bk[b.x])return dfn[a.y]<dfn[b.y];
return bk[a.x]<bk[b.x];
}
bool queryCmp_id(Query a,Query b){
return a.id<b.id;
}
int lca(int u,int v){
if(deep[u]<deep[v])swap(u,v);
for(int i=;~i;i--)
if(deep[fa[u][i]]>=deep[v])
u=fa[u][i];
if(u == v) return u;
for(int i=;~i;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][];
}
int c_cnt[MAX_N];
void MoveToLca(int u){
for(;u!=nowLca;u=fa[u][]){
if(vis[u]){
vis[u]=false;
c_cnt[color[u]]--;
if(!c_cnt[color[u]])ans--;
}else{
vis[u]=true;
if(!c_cnt[color[u]])ans++;
c_cnt[color[u]]++;
}
}
}
int GetAns(int x,int u,int v){
int tlca=lca(u,v);
if(c_cnt[color[tlca]])return x;
else return x+;
} void FirstMo(){
int L=query[].x,R=query[].y;
nowLca=lca(L,R);
MoveToLca(L);
MoveToLca(R);
query[].ans=GetAns(ans,L,R);
lastL=L;lastR=R;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
allColor.clear();
//read colors
for(int i=;i<=n;i++){
scanf("%d",&color[i]);
allColor.push_back(color[i]);
}
//Discretization the color
sort(allColor.begin(),allColor.end());
it=unique(allColor.begin(),allColor.end());
allColor.resize(distance(allColor.begin(),it));
for(int i=;i<=n;i++){
color[i]=lower_bound(allColor.begin(),allColor.end(),color[i])-allColor.begin()+;
}
//read the tree
memset(lin,,sizeof(lin));
e_cnt=;
for(int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
insert(u,v);
insert(v,u);
}
//divide in blocks
//prepare for lca: get deep, dfs order, get father
b_len=sqrt((double)n);
b_cnt=;
n_cnt=;
top=;
deep[]=,deep[]=;
memset(fa,,sizeof(fa));
memset(dfn,,sizeof(dfn));
memset(vis,,sizeof(vis));
memset(stack,,sizeof(stack));
dfs();
b_cnt++;
while(top){
bk[stack[top--]]=b_cnt;
}
for(int i = ; (<<i) <= n; i++)
for(int j = ; j <= n; j++)
fa[j][i] = fa[fa[j][i-]][i-];
//read the query
for(int i=;i<=m;i++){
scanf("%d%d",&query[i].x,&query[i].y);
query[i].id=i;
if(dfn[query[i].x]>dfn[query[i].y])
swap(query[i].x,query[i].y);
}
//mo's algorithm
sort(query+,query+m+,queryCmp_xkb_ydfn);
memset(vis,,sizeof(vis));
memset(c_cnt,,sizeof(c_cnt));
lastL=,lastR=,ans=;
for(int i=;i<=m;i++){
int L=query[i].x,R=query[i].y;
nowLca=lca(L,lastL);
MoveToLca(L);
MoveToLca(lastL);
nowLca=lca(R,lastR);
MoveToLca(R);
MoveToLca(lastR);
query[i].ans=GetAns(ans,L,R);
lastL=L;lastR=R;
}
sort(query+,query+m+,queryCmp_id);
for(int i=;i<=m;i++){
printf("%d\n",query[i].ans);
}
}
return ;
}
wa了无数发,最后发现是dfs的时候用vis数组判断点是否访问过,结果忘记初始化vis[1]了。。。。好蠢,后来改成了直接用dfn数组判断是否访问过了,本意是节省资源,结果居然A了。。。人生处处是惊喜。
这里顺便总结下lca写法吧。
这里的是倍增法求LCA
int fa[MAX_N][20],deep[MAX_N];
int dfn[MAX_N];void dfs(int u){
dfn[u]=++n_cnt;
for(int i=lin[u];i;i=e[i].next){
int v=e[i].y;
if(!dfn[v]){
fa[v][0]=u;
deep[v]=deep[u]+1;
dfs(v);
}
}
}
int lca(int u,int v){
if(deep[u]<deep[v])swap(u,v);
for(int i=17;~i;i--)
if(deep[fa[u][i]]>=deep[v])
u=fa[u][i];
if(u == v) return u;
for(int i=17;~i;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}int main()
{
n_cnt=0;
deep[0]=0,deep[1]=1;
memset(fa,0,sizeof(fa));
memset(dfn,0,sizeof(dfn));
dfs(1);for(int i = 1; (1<<i) <= n; i++)
for(int j = 1; j <= n; j++)
fa[j][i] = fa[fa[j][i-1]][i-1];
return 0;
}
dfn换成vis也是一样的
首先初始化deep数组表示节点深度,然后是fa[i][j]表示节点i的第2^j的父亲节点是什么,
先dfs求出deep和直系父亲
然后双重循环处理fa数组
lca的时候,先对齐u和v,就是让他们处于同一深度,然后一起向上,直到lca的儿子为止,返回他的父亲,就是lca。
最新文章
- ZXingObjC 64位 集成到自己的项目中(xcode 6.4)
- 设置Tomcat应用自动部署目录
- IOS开发—IOS 8 中设置applicationIconBadgeNumber和消息推送
- Android 开源项目android-open-project解析之(三) ScrollView,TimeView,TipView,FlipView
- 在浏览器中输入Google.com并且按下回车之后发生了什么?
- poj 3265 Problem Solving dp
- poj3928 la4329 pingpong
- linux下新建svn项目
- L2-016. 愿天下有情人都是失散多年的兄妹(深搜)*
- DS树+图综合练习--二叉树之最大路径
- 第一次php之旅
- CSS 绝对定位与弹性布局合作居中
- hihocoder #1301 : 筑地市场 二分+数位dp
- S 联系人新增及更新
- thinkphp5登录并保存session、根据不同用户权限跳转不同页面
- django【ORM】 通过外键字段找对应类
- ASP.NET基础学习(暴力破解密码)
- android 内存分哪些区
- Python-PyQt4学习资料汇总
- 在Virtualbox虚拟机中配置使用ROS Spark机器人(Orbbec Astra 和 Xtion)
热门文章
- C#中大批量导入数据SqlBulkCopy
- C#中null、";";、string.empty区别
- apache出现You don&#39;t have permission to access / on this server提示的解决方法
- 实验6 Bezier曲线生成
- 03--软件包管理工具 apt
- .bat 打开程序
- Auto Layout压缩阻力及内容吸附讲解
- java 如何将异常Exception的信息转换为String
- MongoDB经典入门(1)--安装
- 10件5G能实现,但4G不能做的事情