HDU 4912 LCA+策略_hdu4912-程序员宅基地

技术标签: 线段树  图论  hdu  LCA  ACM  

点击打开链接

题意:给了一个树,然后m条路径,问最多可以选多少条路径而没有一个点是重复使用的,如第二组样例,3条路径是4—2—5和6—3—7和2—1—3,那么只能选前两个使得所选路径最多

思路:没啥思路,看了正解竟然是LCA+贪心,好嘛可以这样考虑,对于所有的可选路径,我们先选择最下面的对上面是没有影响的,那么我们可以对每条路经的最上面的那个点进行排序,就按深度由大到小排序,然后这个最上面的点不就是LCA嘛,然后因为是由下到上的,那么对于每次之后就要将以LCA为根的子树节点全部标记,因为它作为深度最深的点以后它的下面在出现肯定是不符合的了       PS:主要是不敢去想用贪心,自己就是想当然的写根本不知道这么贪心对不对(弱哭)

#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=100010;
bool vis[maxn];
int L[maxn*2],E[maxn*2],H[maxn],dis[maxn],dp[2*maxn][20],num[maxn],head[maxn],kkk,pre[maxn];
struct node{
    int to,next;
}EE[maxn*10];
void add_edge(int u,int v){
    EE[kkk].to=v;EE[kkk].next=head[u];head[u]=kkk++;
}
int k,n;
void dfs(int t,int deep){
    k++;E[k]=t;L[k]=deep;H[t]=k;
    for(int i=head[t];i!=-1;i=EE[i].next){
        int tt=EE[i].to;
        if(!vis[tt]){
            vis[tt]=1;pre[tt]=t;
            dfs(tt,deep+1);
            k++;E[k]=t;L[k]=deep;
        }
    }
}
void RMQ_init(){
    for(int i=1;i<=2*n-1;i++) dp[i][0]=i;
    for(int i=1;(1<<i)<=2*n-1;i++){
        for(int j=1;j+(1<<i)-1<=2*n-1;j++){
            if(L[dp[j][i-1]]<L[dp[j+(1<<(i-1))][i-1]]) dp[j][i]=dp[j][i-1];
            else dp[j][i]=dp[j+(1<<(i-1))][i-1];
        }
    }
}
int RMQ(int le,int ri){
    le=H[le];ri=H[ri];
    if(le>ri) swap(le,ri);
    int kk=0;
    while((1<<(kk+1))<=ri-le+1) kk++;
    if(L[dp[le][kk]]<L[dp[ri-(1<<kk)+1][kk]]) return E[dp[le][kk]];
    else return E[dp[ri-(1<<kk)+1][kk]];
}
struct edge{
    int f,x,y;
}tmp[maxn];
bool cmp(const edge &a,const edge &b){
    return L[H[a.f]]>L[H[b.f]];
}
void visdfs(int x){
    vis[x]=1;
    for(int i=head[x];i!=-1;i=EE[i].next){
        int t=EE[i].to;
        if(t==pre[x]||vis[t]) continue;
        visdfs(t);
    }
}
int main(){
    int q,u,v;
    while(scanf("%d%d",&n,&q)!=-1){
        for(int i=0;i<=n;i++) vis[i]=0;
        memset(head,-1,sizeof(head));
        for(int i=0;i<n-1;i++){
            scanf("%d%d",&u,&v);
            add_edge(u,v);add_edge(v,u);
        }
        kkk=0;k=0;vis[1]=1;dfs(1,1);RMQ_init();
        for(int i=1;i<=q;i++){
            scanf("%d%d",&u,&v);
            int en=RMQ(u,v);
            tmp[i].f=en;tmp[i].x=u;tmp[i].y=v;
        }
        int ans=0;
        for(int i=1;i<=n;i++) vis[i]=0;
        sort(tmp+1,tmp+1+q,cmp);
        for(int i=1;i<=q;i++){
            if(vis[tmp[i].x]==0&&vis[tmp[i].y]==0){
                ans++;
                int uu=tmp[i].x,vv=tmp[i].y,ff=tmp[i].f;
                visdfs(ff);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Dan__ge/article/details/51776933

智能推荐

第一、UITableView的使用大全-程序员宅基地

文章浏览阅读1.1k次。首先、对UITableView进行讲解,下面有对它进行实际的应用UITableView 显示大型内容的列表 单行,多列 垂直滚动,没有水平滚动 大量的数据集 性能强大,而且普遍存在于iPhone的应用程序中TableVie

使用redis存储kafka的偏移量_kafka redis 偏移-程序员宅基地

文章浏览阅读1.5k次。使用redis存储kafka的偏移量转自:Lu_Xiao_Yue使用Redis来记录偏移量,以前用receive方式时,使用zookeeper保存偏移量,不用自己保存偏移量,使用直连方式可以自己保存偏移量,更加灵活。在直连方式中,保存偏移量可以使用zookeeper,也可以使用mysql、redis等来保存偏移量,下面使用一种简单的方式用reids来保存偏移量package day03.Ka..._kafka redis 偏移

SPSS新手教程——对问卷数据进行处理之样本分布_spss样本在性别与年龄上的分布状态-程序员宅基地

文章浏览阅读8.1k次,点赞2次,收藏64次。在刚刚开始着手于一项研究时,利用问卷调查收集数据无疑是大多数人的选择,而如何处理收集到的数据有很多种方法,其中利用IBM SPSS Statistics软件来进行处理是比较方便且实用的,IBM SPSS Statistics软件的界面属于用户友好型,操作起来也较为简易。本次我们主要探讨如何对收集到的数据进行样本分布研究,以及如何建立样本分布表。一、打开数据文件本例中使用的是关于社交媒体使用情况对大学生自我评价影响的研究问卷所收集到的数据。首先对数据进行整理,将问卷中的问题放在列中,并根据问题对其_spss样本在性别与年龄上的分布状态

python for ArcGIS 绘制西安市板块地图_西安gis区域图-程序员宅基地

文章浏览阅读1.1k次。python for ArcGIS 绘制西安市板块地图_西安gis区域图

BIOS追code之PEI phase_pei阶段-程序员宅基地

文章浏览阅读7k次,点赞13次,收藏38次。SEC 阶段总述PEI阶段的功能任务:PEI划分:PEI阶段执行流程:PEI阶段执行流程描述及流程图阶段总述PEI(Pre-EFI Initialization,预先EFI初始化),虽然SEC阶段对CPU和CPU内的资源进行了初始化,但是PEI阶段可用的资源依旧十分有限,该阶段对内存进行初始化,主要功能是为DXE阶段准备执行环境,将所需要传递给DXE的信息组成HOB(Hand Off Block)列表,最终将控制权转交到DXE。UEFI具有模块化设计的特点,PEI就是一个模块。PEI Image的入口_pei阶段

介绍个好用的内网穿透工具:nps-程序员宅基地

文章浏览阅读6.4k次,点赞2次,收藏15次。最早开始接触内网穿透,是在调试微信支付的时候,微信需要回调一个公网地址,经过一番搜索,我选用了 natapp,优点是有免费隧道,缺点是公网域名和端口是随机分配的,偶尔调试用下还可以。后来,因为要映射公司和家里 Windows 远程连接的端口,natapp 那种随机域名和端口的服务,不满足我的需求。这时 frp 出现在可选列表里,只需要一台公网服务器,就可以搭建,通过服务端和客...

随便推点

梦幻星空html,制作梦幻星空效果图的滤镜教程-程序员宅基地

文章浏览阅读149次。一、把图像处理软件Photoshop打开,执行CTRL+N新建一个宽度和高度都为500像素的RGB图像,用黑色填充背景图层,再使用白色画笔工具在图像中点出一些白色的小圆点,这样看起来就像是满天的星星,刚好作为我们梦幻星空的背景图。二、执行菜单栏上的“视图-标尺”命令(快捷键:CTRL+R),显示出标尺以后,参考标尺上的刻度,在图像的中心分别拉出一条水平和垂直的参考线,然后创建一个新的图层,按住SH..._html梦幻星空

Data URL和图片_data url图片-程序员宅基地

文章浏览阅读1.7k次。Data URL给了我们一种很巧妙的将图片“嵌入”到HTML中的方法。跟传统的用img标记将服务器上的图片引用到页面中的方式不一样,在Data URL协议中,图片被转换成base64编码的字符串形式,并存储在URL中,冠以mime-type。本文中,我将介绍如何巧妙的使用Data URL优化网站加载速度和执行效率。Data URL基本原理为什么Data URL是个好东西_data url图片

iOS 用内置浏览器Safari 打开网页_xcode safariservices打开网址-程序员宅基地

文章浏览阅读9.5k次。iOS 开发的时候,我们需要打开某个网页,可以写一个web页面,也可直接使用浏览器打开网址那么我们怎么样使用iOS 内置的浏览器打开网址呢?如下:ios 10 之前使用[[UIApplication sharedApplication]openURLopenURL:打开的网址NSURL *URL = [NSURL URLWithString:@"http://ww..._xcode safariservices打开网址

Android7.0中文文档 --- EditText_edittext的getaccessibilityclassname-程序员宅基地

文章浏览阅读1k次。android中文文档 EditView_edittext的getaccessibilityclassname

Linux ubuntu 安装maven_linux unbtu 安装maven-程序员宅基地

文章浏览阅读217次。首先去maven官网下载maven压缩包(此时最新版本为3.6.3)(PS:如果不是root权限,记得加 sudo )创建存放maven的新目录mkdir /usr/local/maven通过FTP工具或者XFTP工具把压缩包传输到指定目录,然后进入该目录解压缩cd /usr/local/maventar -xzvf apache-maven-3.6.3-b..._linux unbtu 安装maven

SpringSecurityOauth2+JWT实现单点登录_spring security oauth2 jwt 单点登录-程序员宅基地

文章浏览阅读3k次,点赞7次,收藏28次。单点登录的介绍单点登录(Single Sign On),简称为 SSO,SSO的定义是在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统。OAuth2 相关解释Resource owner(资源拥有者):拥有该资源的最终用户,他有访问资源的账号密码;Resource server(资源服务器):拥有受保护资源的服务器,如果请求包含正确的访问令牌,可以访问资源;Clie..._spring security oauth2 jwt 单点登录

推荐文章

热门文章

相关标签