清北学堂模拟赛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)
blank

相关推荐

发表回复

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

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