New Barns
New Barns
时间限制: 1 Sec 内存限制: 128 MB
题目描述
Whenever FJ constructs a new barn, he
connects it with at most one bidirectional pathway to an existing barn.
In order to make sure his cows are spread sufficiently far apart, he
sometimes wants to determine the distance from a certain barn to the
farthest possible barn reachable from it (the distance between two barns
is the number of paths one must traverse to go from one barn to the
other).
FJ will give a total of Q (1≤Q≤105)
queries, each either of the form "build" or "distance". For a build
query, FJ builds a barn and links it with at most one previously built
barn. For a distance query, FJ asks you the distance from a certain barn
to the farthest barn reachable from it via a series of pathways. It is
guaranteed that the queried barn has already been built. Please help FJ
answer all of these queries.
输入
first line contains the integer Q. Each of the next Q lines contains a
query. Each query is of the form "B p" or "Q k", respectively telling
you to build a barn and connect it with barn pp, or give the farthest
distance, as defined, from barn k. If p=−1, then the new barn will be
connected to no other barn. Otherwise, p is the index of a barn that has
already been built. The barn indices start from 1, so the first barn
built is barn 1, the second is barn 2, and so on.
输出
write one line of output for each distance query. Note that a barn
which is connected to no other barns has farthest distance 0.
样例输入
7
B -1
Q 1
B 1
B 2
Q 3
B 2
Q 2
样例输出
0
2
1
提示
The example input corresponds to this network of barns:
(1)
\
(2)---(4)
/
(3)
In query 1, we build barn number 1. In query 2, we ask for the distance
of 1 to the farthest connected barn. Since barn 1 is connected to no
other barns, the answer is 0. In query 3, we build barn number 2 and
connect it to barn 1. In query 4, we build barn number 3 and connect it
to barn 2. In query 5, we ask for the distance of 3 to the farthest
connected barn. In this case, the farthest is barn 1, which is 2 units
away. In query 6, we build barn number 4 and connect it to barn 2. In
query 7, we ask for the distance of 2 to the farthest connected barn.
All three barns 1, 3, 4 are the same distance away, which is 1, so this
is our answer.
分析：题意：给定一个森林，在建森林的过程中有一些询问，距离某个点最远的点的距离；
考虑分治，对于每个点的祖先，要么经过祖先，要么不经过；
如果经过，考虑维护这个祖先的最大的两个点的深度，这两个点不在同一棵子树且已经被标记；更新答案分在不在同一子树里即可；
如果不经过，则可以递归到子树，对于分治来说，维护重心，每个点有log个祖先；
注意如果两个点被标记则lca也被标记过；
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+,mod=1e9+,inf=0x3f3f3f3f;
int n,m,k,t,rt,a[maxn],sz[maxn],all;
bool vis[maxn];
vector<int>e[maxn];
struct node
{
int mx1,mx2,mxid;
vector<pair<int,int> >anc;
}p[maxn];
int getroot(int x,int y=)
{
for(int i=;i<e[x].size();i++)
{
int z=e[x][i];
if(z==y||vis[z])continue;
if(sz[z]*>=all)return getroot(z,x);
}
return x;
}
void getdep(int x,int y,int dep)
{
p[x].anc.push_back({rt,dep});
for(int i=;i<e[x].size();i++)
{
int z=e[x][i];
if(z==y||vis[z])continue;
getdep(z,x,dep+);
}
}
void getsz(int x,int y=)
{
sz[x]=;
for(int i=;i<e[x].size();i++)
{
int z=e[x][i];
if(z==y||vis[z])continue;
getsz(z,x);
sz[x]+=sz[z];
}
}
void dfs(int x)
{
getsz(x);
all=sz[x];
rt=getroot(x);
getdep(rt,,);
vis[rt]=true;
for(int i=;i<e[rt].size();i++)
{
int z=e[rt][i];
if(!vis[z])dfs(z);
}
}
int main()
{
int i,j;
scanf("%d",&m);
int pos=;
for(i=;i<=m;i++)
{
char str[];
scanf("%s%d",str,&n);
if(str[]=='B')
{
a[i]=++pos;
if(n==-)continue;
else e[n].push_back(pos),e[pos].push_back(n);
}
else a[i]=-n;
}
for(i=;i<=pos;i++)if(!vis[i])dfs(i);
pos=;
for(i=;i<=m;i++)
{
int last=-;
if(a[i]>)
{
++pos;
for(j=p[pos].anc.size()-;j>=;j--)
{
int fa=p[pos].anc[j].first,w=p[pos].anc[j].second;
if(p[fa].mx1<=w)
{
if(p[fa].mxid!=last)p[fa].mx2=p[fa].mx1;
p[fa].mx1=w;
p[fa].mxid=last;
}
else if(p[fa].mx2<=w)
{
if(last!=p[fa].mxid)p[fa].mx2=w;
}
last=fa;
}
}
else
{
int now=-a[i];
int ret=p[now].mx1;
for(j=p[now].anc.size()-;j>=;j--)
{
int fa=p[now].anc[j].first,w=p[now].anc[j].second;
if(fa>pos)
{
last=fa;
continue;
}
if(last==p[fa].mxid)ret=max(ret,w+p[fa].mx2);
else ret=max(ret,w+p[fa].mx1);
last=fa;
}
printf("%d\n",ret);
}
}
return ;
}
最新文章
- html javascript css3 php3.2.3离线手册
- 学习MySQL之数据类型（四）
- 如何转换SQL Server 2008数据库到SQL Server 2005
- 关于SQL Server无法查询中文的问题
- 爱拼图游戏android源码完整版
- MongoDB Enterprise提供的服务
- POJ 1308 Is It A Tree? (并查集)
- 与非CCR代码互操作
- Subline Text快捷键
- poj 3258 River Hopscotch 二分
- 使用jQuery的attr方法来修改onclick值
- MATLAB编译器
- Gentoo挂载ntfs的NTFS分区
- 漫话JavaScript与异步·第二话——Promise：一诺千金
- 【python学习笔记】4.字典：当索引不好用时
- RAxML安装
- Visual Studio 开发（一）：安装配置Visual Studio Code
- 4.请介绍一下c++和Java的区别
- 数据仓库分层ODS DW DM 主题 标签
- Python 快速排序 算法