清北学堂模拟赛d3t6 c

清北学堂模拟赛d3t6 c分析:比较神奇的一道题.要把树变成环肯定要先变成链,然后把链给拼接成环.接下来考虑一个脑洞大开的树形dp:设f[i][0]表示i不与父节点相连的链数,f[i][1]表示i与父节点相连的链数,先考虑怎么

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

清北学堂模拟赛d3t6 c

分析:比较神奇的一道题.要把树变成环肯定要先变成链,然后把链给拼接成环.接下来考虑一个脑洞大开的树形dp:设f[i][0]表示i不与父节点相连的链数,f[i][1]表示i与父节点相连的链数,先考虑怎么转移f[i][0],如果i不与父节点相连,那么i肯定与两个子节点相连,其它的子节点都不与父节点相连,而且要剪掉与父亲节点的一条边,所以f[i][0] = (Σf[j][0]) – f[p][0] – f[q][0] + f[p][1] + f[q][1] – 1.f[i][1]也能很容易推导出来f[i][1] = (Σf[j][0]) – f[p][0] + f[p][1].这两个式子中的p,q使我们选出来与i组成链的子节点,为了使得f[i][0/1]最小,我们要选出使f[j][1] – f[j][0]最小的p,q,这个在枚举的时候扫一下就可以了.

     最后是合并,一个树有N-1条边,先不断地删边,然后加边,加到N-1条边,最后再补一条边形成一个环,可以发现删边和加边是对称的,需要删掉链-1条边,那么也需要加上链-1条边,最后用一条边形成一个环就可以了.

树形dp,考虑好链的种类和怎么从子节点转移,充分利用好加边和删边的对称性,就能A掉此题,最关键的还是状态的表示,树形dp可能会需要保存不同的状态,如果对于当前状态推不下去了,就多加点状态,直到可做为止.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int inf = 0x7fffffff;

int n, head[100010], to[200010], nextt[200010], tot = 1, f[100010][2];

void add(int x, int y)
{
    to[tot] = y;
    nextt[tot] = head[x];
    head[x] = tot++;
}

void dfs(int u, int from)
{
    int min1 = inf, min2 = inf,son = 0,sum = 0,sum2 = 0;
    for (int i = head[u]; i; i = nextt[i])
    {
        int v = to[i];
        if (v != from)
        {
            dfs(v, u);
            son++;
            sum += f[v][0];
            sum2 += f[v][1];
            int temp = f[v][1] - f[v][0];
            if (temp < min1)
            {
                min2 = min1;
                min1 = temp;
            }
            else
                if (temp < min2)
                    min2 = temp;
        }
    }
    if (son == 0)
        f[u][0] = f[u][1] = 1;
    if (son == 1)
        f[u][0] = f[u][1] = sum2;
    else
        if (son >= 2)
        {
        f[u][0] = sum + min1 + min2 - 1;
        f[u][1] = sum + min1;
        }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs(1, 0);
    printf("%d\n", f[1][0] * 2 - 1);

    return 0;
}

 

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

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

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

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

(0)


相关推荐

  • linux rsyslogd cpu占用率高问题「建议收藏」

    linux rsyslogd cpu占用率高问题「建议收藏」最近有几次,linuxcentos7服务停了后,重启,再起一些应用后,查看top后,rsyslogdcpu占用率高问题,先说我这块怀疑导致的原因吧。原因很有可能是当前机器的系统盘挂载出现问题,或者系统盘有磁道坏了,导致,在启动某个软件时,一直在记录日志。现象top命令看下一:解决发现rsyslog可以理解为增强版的syslog,可以支持输出日志到各种数据库,使用RELP+TCP实现数据的传输,对目前的服务器服务而言,可以关闭该进程。#第一步:重启rsyslog服务,

  • 覆盖,交换技术和虚拟存储技术的区别在于_虚拟存储技术的目的

    覆盖,交换技术和虚拟存储技术的区别在于_虚拟存储技术的目的操作系统—覆盖,交换技术和虚拟存储技术的区别

  • 生存分析(Survival Analysis)、Cox风险比例回归模型(Cox proportional hazards model)及「建议收藏」

    生存分析(Survival Analysis)、Cox风险比例回归模型(Cox proportional hazards model)及「建议收藏」生存分析(SurvivalAnalysis)、Cox风险比例回归模型(Coxproportionalhazardsmodel)及C-index1.生存分析生存分析指的是一系列用来探究所感兴趣的事件的发生的时间的统计方法。常见的有1)癌症患者生存时间分析2)工程中的失败时间分析等等。1.1定义给定一个实例iii,我们用一个三元组来表示(Xi,δi,Ti)(X_i,\del…

  • c语言格式化输出「建议收藏」

    c语言格式化输出「建议收藏」C语言printf指定宽度的格式化输出printf()是一个标准库函数,使用时需要include头文件stdio.h。#include<stdio.h>printf()函数的调用形式为:printf(“格式控制字符串”,输出列表);其中,格式控制字符串用于指定输出格式,有格式字符串和非格式字符串两种形式。格式字符串有%,%后面跟着各种格式字符,用以说明输出数据的类型、形式、长度、小数位等。下面是一些常用的指定宽度的格式化输出例子。格式化占位符(format):%[

  • python输出unicode编码_Python以utf8编码读取文件

    python输出unicode编码_Python以utf8编码读取文件withopen(self.path,’r’)astest:forlineintest:pass代码如上,出现错误:UnicodeDecodeError:’gbk’codeccan’tdecodebyte0x80inposition…UnicodeDecodeError:’gbk’codeccan’tdecodebyte0x80inposition9:…或者是UnicodeDecodeErr..

  • Ubuntu RabbitVCS

    Ubuntu RabbitVCSsudoadd-apt-repositoryppa:rabbitvcs/ppasudoapt-getupdatesudoapt-getinstallrabbitvcs-corerabbitvcs-nautilus3rabbitvcs-clinautilus-q转载于:https://www.cnblogs.com/ouuy/archive/2012…

发表回复

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

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