hdu 4912 Paths on the tree(lca+馋)

hdu 4912 Paths on the tree(lca+馋)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

意甲冠军:它使树m路径,当被问及选择尽可能多的路径,而这些路径不相交。

思考:贪心,比較忧伤。首先求一下每对路径的lca。依照lca的层数排序。在深一层的优先级高。那么就能够贪心了,每次选择层数最深的那一个,假设两个端点没有被标记,那么就选择这条路径,把lca的子树都标记掉。

代码:

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn=100000+10;
struct Edge
{
    int v,next;
    Edge(int v=0,int next=0):v(v),next(next){}
}edges[maxn<<1];
struct Node
{
    int u,v,id;
    Node(int u=0,int v=0,int id=0):u(u),v(v),id(id) {}
}node[maxn];
int head[maxn],nEdge;
int LCA[maxn],pa[maxn],d[maxn];
bool vis[maxn];
vector<pair<int,int> >querys[maxn];
int Find(int x)
{
    return x==pa[x]?x:pa[x]=Find(pa[x]);
}
void AddEdges(int u,int v)
{
    edges[++nEdge]=Edge(v,head[u]);
    head[u]=nEdge;
    edges[++nEdge]=Edge(u,head[v]);
    head[v]=nEdge;
}
void dfs(int u,int fa)
{
    pa[u]=u;
    pair<int,int>pii;
    for(int i=0;i<(int)querys[u].size();++i)
    {
        pii=querys[u][i];
        if(d[pii.first]==-1) continue;
        LCA[pii.second]=Find(pii.first);
    }
    for(int k=head[u];k!=-1;k=edges[k].next)
    {
        int v=edges[k].v;
        if(v==fa) continue;
        d[v]=d[u]+1;
        dfs(v,u);
        pa[v]=u;
    }
}
bool cmp(Node a,Node b)
{
    int u=LCA[a.id];
    int v=LCA[b.id];
    return d[u]>d[v];
}
void Init(int n)
{
    memset(vis,0,sizeof(vis));
    memset(head,0xff,sizeof(head));
    nEdge=-1;
    memset(d,0xff,sizeof(d));
    for(int i=0;i<=n;++i)
        querys[i].clear();
}
void tour(int u)
{
    vis[u]=true;
    for(int k=head[u];k!=-1;k=edges[k].next)
    {
        int v=edges[k].v;
        if(vis[v]||d[v]<d[u]) continue;
        tour(v);
    }
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        Init(n);
        int u,v;
        for(int i=1;i<n;++i)
        {
            scanf("%d%d",&u,&v);
            AddEdges(u,v);
        }
        for(int i=0;i<m;++i)
        {
            scanf("%d%d",&u,&v);
            querys[u].push_back(make_pair(v,i));
            querys[v].push_back(make_pair(u,i));
            node[i].u=u;node[i].v=v;
            node[i].id=i;
        }
        d[1]=0;
        dfs(1,-1);
        sort(node,node+m,cmp);
        int cnt=0;
        for(int i=0;i<m;++i)
        {
            if(!vis[node[i].u]&&!vis[node[i].v])
            {
                cnt++;
                tour(LCA[node[i].id]);
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

版权声明:本文博主原创文章,博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117044.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • sobel算子实现

    sobel算子实现原理:实现://阶乘intfactorial(intn){ intfac=1; if(n==0) returnfac; for(inti=1;i<=n;++i) fac*=i; returnfac;}//获得Sobel平滑算子MatgetSobelSmooth(intsize){ intn=size-1; MatSobelSmoothoper=Mat::zeros(size,1,CV_32F); fo

  • Optimal Keypad[通俗易懂]

    Optimal Keypad[通俗易懂]Description OptimusMobilesproducesmobilephonesthatsupportSMSmessages.TheMobileshaveakeypadof12keys,numbered1to12.Thereisacharacterstringassignedtoeachkey.Totypeinthe

  • 商品搜索引擎—分词(插件介绍与入门实例)

    商品搜索引擎—分词(插件介绍与入门实例)

    2020年11月12日
  • 小米手机通过电脑上网「建议收藏」

    小米手机通过电脑上网「建议收藏」步骤很简单。只需要两步。所需要的软件工具如下:  电脑软件1.小米USB驱动  手机软件2.超级终端 点击下载  1.打开系统设置-系统-共享手机网络-USB绑定-(打开)  2.USB连接上电脑,在网络连接里会多出一个本地连接4,然后找到一下你的宽带连接(电脑上网那个)点一下右键-属性-共享-允许其他网络用户通过此计算器…选择勾上。  然后找到虚拟网卡(就是第二

    2022年10月30日
  • python最长回文子串动态规划_最长回文子串问题

    python最长回文子串动态规划_最长回文子串问题问题描述回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。输入一个字符串Str,输出Str里最长回文子串的长度。方法一:暴力求解遍历每一个子串,再判断这个子串是不是回文串,最后判断这个串是不是最长的回文子串。遍历子串的复杂度是O(n^2),判断是不是回文串的复杂度是O(n),所以这个算法的复杂度是O(n^3)。方法二:动态规划法用一个二维的数组ai来表示从第i位到第j位的子…

  • 剑指 Offer 09. 用两个栈实现队列「建议收藏」

    剑指 Offer 09. 用两个栈实现队列「建议收藏」用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )示例 1:输入:[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”][[],[3],[],[]]输出:[null,null,3,-1]示例 2:输入:[“CQueue”,“deleteHead”,“appendTail”,“ap

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号