文档章节

【codevs 2370】小机房的树

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 335
阅读 11
收藏 0

这个是题目吗
简单的lca,难度在于给数组命名
个人的想法是记录到根的距离,ans = dis[a] + dis[b] - dis[lca(a,b)] - dis[lca(a,b)]

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 50000 + 5;
const int LOG = 25;
int n,m;
struct edge
{
    int f,t,v;
}l[MAXN * 2];
int first[MAXN],next[MAXN * 2],tot;
void init()
{
    memset(first,0xfff,sizeof(first));
    tot = 0;
    return;
}
void build(int f,int t,int v)
{
    l[++tot] = (edge){f,t,v};
    next[tot] = first[f];
    first[f] = tot;
    return;
}
int anc[MAXN][LOG],deep[MAXN],rank[MAXN];
void make_tree(int x,int f,int v)
{
    anc[x][0] = f;
    deep[x] = deep[f] + 1;
    rank[x] = v;
    for(int i = first[x];i != -1;i = next[i])
        if(l[i].t != f)
            make_tree(l[i].t,x,v + l[i].v);
    return;
}
void make_lca()
{
    for(int j = 1;j <= log2(n);j ++)
        for(int i = 1;i <= n;i ++)
            anc[i][j] = anc[anc[i][j-1]][j-1];
    return;
}
int lca(int x,int y)
{
    if(deep[x] < deep[y])
        swap(x,y);
    for(int i = log2(n);i >= 0;i --)
        if(deep[anc[x][i]] >= deep[y])
            x = anc[x][i];
    if(x == y)
        return x;
    for(int i = log2(n);i >= 0;i --)
        if(anc[x][i] != anc[y][i])
            x = anc[x][i],y = anc[y][i];
    return anc[x][0];
}
int f,t,v;
int main()
{
    init();
    scanf("%d",&n);
    for(int i = 1;i < n;i ++)
    {
        scanf("%d %d %d",&f,&t,&v);
        build(f,t,v);
        build(t,f,v);
    }
    make_tree(0,0,0);
    make_lca();
    scanf("%d",&m);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d %d",&f,&t);
        printf("%d\n",rank[f] + rank[t] - (rank[lca(f,t)] << 1));
    }
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
Duan2baka的各种LCA模板!

(这篇文章是模板向…了解具体思想还是看网上其他详细讲解吧QAQ) LCA,即最近公共祖先,是在有根树中两个点最近的公共祖先,在树上问题中非常有用QAQ 常用LCA求法: 一、树链剖分LCA 树链剖分...

WADuan2
2017/10/17
0
0
用tarjan求最近公共祖先

原文地址https://www.cnblogs.com/JVxie/p/4854719.html LCA 最近公共祖先 Tarjan(离线)算法的基本思路及其算法实现 小广告:METO CODE 安溪一中信息学在线评测系统(OJ)       //由于这...

weixin_39872717
2017/11/09
0
0
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0
codevs4438 YJQ Runs Upstairs

Description 学校科技楼一共有 层,而神犇YJQ每天都在科技楼 楼的机房写代码。这天,他准备从科技楼 楼爬到 楼。有个 连接不同楼层的楼梯,爬每个楼梯需要一定的体力值。楼梯一定是从低处通往高...

aziint
2018/01/06
0
0
主席树学习笔记(poj2104,bzoj1901/zoj2112)

前言 千辛万苦才明白主席树是什么东西,同机房的jar形把我坑害得好惨......另外,网上的主席树资料都很精炼啊,像我这种蒟蒻怎么可能看的懂,不过总算是找到了一些好资料。 主席树的原理 同机...

litble
2017/04/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Taro 兼容 h5 踩坑指南

最近一周在做 Taro 适配 h5 端,过程中改改补补,好不酸爽。 本文记录📝遇到的问题,希望为有相同需求的哥们👬节约点时间。 Taro 版本:1.3.9。 解决跨域问题 h5 发请求会报跨域问题,需...

dkvirus
今天
4
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888
今天
3
0
hash slot(虚拟桶)

在分布式集群中,如何保证相同请求落到相同的机器上,并且后面的集群机器可以尽可能的均分请求,并且当扩容或down机的情况下能对原有集群影响最小。 round robin算法:是把数据mod后直接映射...

李朝强
今天
4
0
Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
今天
19
0
java数据类型

基本类型: 整型:Byte,short,int,long 浮点型:float,double 字符型:char 布尔型:boolean 引用类型: 类类型: 接口类型: 数组类型: Byte 1字节 八位 -128 -------- 127 short 2字节...

audience_1
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部