hdu 4912 Paths on the tree(树链拆分+贪婪)

hdu 4912 Paths on the tree(树链拆分+贪婪)

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

题目链接:hdu 4912 Paths on the tree

题目大意:给定一棵树,和若干个通道。要求尽量选出多的通道,而且两两通道不想交。

解题思路:用树链剖分求LCA,然后依据通道两端节点的LCA深度排序,从深度最大优先选。推断两个节点均没被标

记即为可选通道。

每次选完通道。将该通道LCA下面点所有标记。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1e5 + 5;

int N, M, E, first[maxn], jump[maxn * 2], link[maxn * 2], vis[maxn];
int id, idx[maxn], top[maxn], far[maxn], son[maxn], cnt[maxn], dep[maxn];

inline void add_Edge (int u, int v) {
    link[E] = v;
    jump[E] = first[u];
    first[u] = E++;
}

void dfs (int u, int pre, int d) {
    far[u] = pre;
    son[u] = 0;
    cnt[u] = 1;
    dep[u] = d;
    for (int i = first[u]; i + 1; i = jump[i]) {
        int v = link[i];
        if (v == pre)
            continue;
        dfs(v, u, d + 1);
        cnt[u] += cnt[v];
        if (cnt[son[u]] < cnt[v])
            son[u] = v;
    }
}

void dfs (int u, int rot) {
    top[u] = rot;
    idx[u] = ++id;
    if (son[u])
        dfs(son[u], rot);
    for (int i = first[u]; i + 1; i = jump[i]) {
        int v = link[i];
        if (v == far[u] || v == son[u])
            continue;
        dfs(v, v);
    }
}

void dfs (int u) {
    if (vis[u])
        return;
    vis[u] = 1;
    for (int i = first[u]; i + 1; i = jump[i]) {
        int v = link[i];
        if (v == far[u])
            continue;
        dfs(v);
    }
}

struct query {
    int u, v, r, d;
    void set(int u, int v, int r, int d) {
        this->u = u;
        this->v = v;
        this->r = r;
        this->d = d;
    }
    friend bool operator < (const query& a, const query& b) {
        return a.d > b.d;
    }
}q[maxn];

int LCA (int u, int v) {
    int p = top[u], q = top[v];
    while (p != q) {
        if (dep[p] < dep[q]) {
            swap(p, q);
            swap(u, v);
        }
        u = far[p];
        p = top[u];
    }
    return dep[u] < dep[v] ? u : v;
}

void init () {
    E = id = 0;
    memset(first, -1, sizeof(first));

    int u, v;
    for (int i = 1; i < N; i++) {
        scanf("%d%d", &u, &v);
        add_Edge(u, v);
        add_Edge(v, u);
    }
    dfs(1, 0, 0);
    dfs(1, 1);

    for (int i = 0; i < M; i++) {
        scanf("%d%d", &u, &v);
        int rot = LCA(u, v);
        q[i].set(u, v, rot, dep[rot]);
    }
    sort(q, q + M);
}

int main () {
    while (scanf("%d%d", &N, &M) == 2) {
        init();

        int ans = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < M; i++) {
            if (vis[q[i].u] || vis[q[i].v])
                continue;
            dfs(q[i].r);
            ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

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

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

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

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

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

(0)


相关推荐

  • 基于USB数据采集卡(DAQ)与IO模块的热电阻温度采集「建议收藏」

    思迈科华针对热电阻温度传感器温度采集的方案热电阻简介这里主要介绍一下铂热电阻,Pt100是铂热电阻,它的阻值跟温度的变化成正比。PT100的阻值与温度变化关系为:当PT100温度为0℃时它的阻值为100欧姆,在100℃时它的阻值约为138.5欧姆。它的工业原理:当PT100在0摄氏度的时候,它的阻值为100欧姆,它的阻值会随着温度上升而成匀速增长。国标热电阻主要接线方式有三种:二线制:在热电阻的两端各连接一根导线来引出电阻信号的方式叫二线制:这种引线方法很简单,但由于连接导线必然存在引线电阻R,电阻

  • 大数据开发基础之Java基础[通俗易懂]

    大数据开发基础之Java基础[通俗易懂]大数据给很多人的感觉是,专业性强,操作繁琐,属于“高大上”的技术。大数据人才供不应求,有一些人则看到了大数据带来的机遇,想通过专业的培训来学习大数据,那么大数据从0开始需要学习些什么内容呢一、0基础学习大数据需要Java基础Java:开发需求最多的编程语言之一,可以从事网站开发、桌面程序设计、游戏开发、安卓后台开发、全栈开发等。它可以说是大数据最基础的编程语言,一是大数据的本质是…

  • java乘法代码_java九九乘法表代码[通俗易懂]

    java乘法代码_java九九乘法表代码[通俗易懂]java九九乘法表代码发布时间:2020-05-2813:34:14来源:亿速云阅读:156作者:鸽子要实现输出99乘法表,我们可以通过两层for循环来实现。具体代码为:publicclassFor99{publicstaticvoidmain(String[]args){for(intm=1;m<=9;m++){for(inti=1;i<=m;i++){inta=…

  • k8s安装使用_setup error怎么解决

    k8s安装使用_setup error怎么解决安装GPG秘钥:curlhttps://mirrors.aliyun.com/kubernetes/apt/doc/apt-key.gpg|sudoapt-keyadd-错误消失

    2022年10月10日
  • K8S架构详解

    K8S架构详解

  • Leetcode 611 javascript Valid Triangle Number

    Leetcode 611 javascript Valid Triangle Number

发表回复

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

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