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)


相关推荐

发表回复

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

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