TTTTTTTTTTTTTTTT #7 div1 A Breadth-First Search by Foxpower 在线LCA(倍增),模拟
Time Limit:2000MS Memory Limit:131072KB 64bit IO Format:%lld & %llu
Description
A - Breadth-First Search by Foxpower
Problem Statement
Fox Ciel went to JAG Kingdom by bicycle, but she forgot a place where she parked her bicycle. So she needs to search it from a bicycle-parking area before returning home.
The parking area is formed as a unweighted rooted tree TT with nn vertices, numbered 11 through nn. Each vertex has a space for parking one or more bicycles. Ciel thought that she parked her bicycle near the vertex 11, so she decided to search it from there by the breadth-first search. That is, she searches it at the vertices in the increasing order of their distances from the vertex 11. If multiple vertices have the same distance, she gives priority to the vertices in the order of searching at their parents. If multiple vertices have the same parent, she searches at the vertex with minimum number at first.
Unlike a computer, she can't go to a next vertex by random access. Thus, if she goes to the vertex jj after the vertex ii, she needs to walk the distance between the vertices ii and jj. BFS by fox power perhaps takes a long time, so she asks you to calculate the total moving distance in the worst case starting from the vertex 11.
Input
The input is formatted as follows.
nn
p2p2 p3p3 p4p4 ⋯⋯ pnpn
The first line contains an integer nn (1≤n≤1051≤n≤105), which is the number of vertices on the unweighted rooted tree TT. The second line contains n−1n−1 integers pipi (1≤pi<i1≤pi<i), which are the parent of the vertex ii. The vertex 11 is a root node, so p1p1 does not exist.
Output
Print the total moving distance in the worst case in one line.
Sample Input 1
4
1 1 2
Output for the Sample Input 1
Sample Input 2
4
1 1 3
Output for the Sample Input 2
Sample Input 3
11
1 1 3 3 2 4 1 3 2 9
Output for the Sample Input
25 题意:一有一棵树,直接相连的节点之间的距离均为1,一个人站在根节点,从深度从低到高搜索,从每次只能把同一深度的搜索完了才能向下一层搜索,问至少需要经过多少距离才能把所有节点都访问一遍
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int inf =0x7f7f7f7f;
const double pi=acos(-1);
const int maxn=100000+10;
int c[maxn][22],deep[maxn],vis[maxn];
vector<vector<int> > G(maxn); void dfs(int u,int par)
{
c[u][0]=par;
for(int i=1;i<=20;i++) c[u][i]=c[c[u][i-1]][i-1];
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==par) continue;
deep[v]=deep[u]+1;
dfs(v,u);
}
} int lca(int u,int v)
{
if(deep[u]<deep[v]) swap(u,v);
for(int i=20;i>=0;i--)
if(deep[c[u][i]]>=deep[v])
u=c[u][i];
if(u==v) return u;
for(int i=20;i>=0;i--)
if(c[u][i]^c[v][i])
{
u=c[u][i];
v=c[v][i];
}
return c[u][0];
} int dis(int u,int v)
{
return deep[u]+deep[v]-2*deep[lca(u,v)];
} int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++) G[i].clear();
deep[1]=0;
for(int i=2;i<=n;i++)
{
int x;scanf("%d",&x);
G[x].push_back(i);
}
dfs(1,1);
int pre=1;ll ans=0;
queue<int> q;
q.push(1);
while(q.size())
{
int u=q.front();q.pop();
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
ans+=dis(pre,v);
pre=v;
q.push(v);
}
}
printf("%lld\n",ans);
}
return 0;
}
分析:LCA倍增法的第一题,需要设置一个pre代表先前处于哪个位置,然后对于当前需要访问的节点u,求pre和u之间的距离就好,通过lca来求
最新文章
- I2C子系统之驱动SSD1306 OLED
- 【BZOJ-4631】踩气球 线段树 + STL
- mybatis跨XML引用
- 【Linux】依赖包检查
- poj1789 Truck History
- tcp的三次握手及四次挥手(连接与中断流程)
- ZOJ 1455 Schedule Problem(差分约束系统)
- 鸟哥的linux私房菜——第12章 正则表达式与文件格式化处理
- Java Object 构造方法的执行顺序
- 利用智能手机(Android)追踪一块磁铁(转)
- .Net开发的两个小技巧
- Java 读书笔记 (五) 目标数据类型转换
- 多功能设备mfd驱动
- Hibernate的入门(概念1):
- linux 分区方案
- android mat 转 bitmap
- 443. String Compression
- sqlserver 更新通过 select 查询出的结果集
- iptables后,外网访问网站可以,内网无法访问【已解决】
- python模块(4)