【JZOJ5262】【GDOI2018模拟8.12】树(DP,性质题)

Description

这里写图片描述

Solution

首先我们可以知道两个性质:1、路径u-v和路径v-w可以合并为路径u-w;2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换)
那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。
我们设f[i]表示满足i子树的需求i上的值要是多少。
那么枚举i的所有儿子,判断a[i]-f[i],看看当前是需要增大还是需要变小,然后再看看哪一个的编号大,判断路径方向,然后更新in和out(表示出度和入度)
然后起点终点去个min减一下就知道每个点做起点或终点多少次了,然后把所有的起点和终点排一次序,两两连接就好了。

Code

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
#define rep(i,a) for(i=first[a];i;i=next[i])
using namespace std;
const int maxn=1e6+7;
int i,j,k,l,t,n,m,ans,head,tail,x,y,z,fu;
int first[maxn*2],last[maxn*2],next[maxn*2],num,a[maxn];
int f[maxn],d[maxn],fa[maxn],in[maxn],out[maxn];
int b[maxn],c[maxn];
void add(int x,int y){
    last[++num]=y,next[num]=first[x],first[x]=num;
}
int main(){
//  freopen("fan.in","r",stdin);
//  freopen("fan.out","w",stdout);
    scanf("%d",&n);
    fo(i,1,n)scanf("%d",&a[i]);
    fo(i,1,n-1)scanf("%d%d",&k,&l),add(k,l),add(l,k);
    head=0,d[tail=1]=1;
    while(head<tail){
        rep(i,d[++head]){
            if(last[i]==fa[d[head]])continue;
            fa[last[i]]=d[head];d[++tail]=last[i];
        }
    }
    fod(k,n,1){
        x=d[k];
        rep(i,x){
            y=last[i];if(y==fa[x])continue;
            z=a[y]-f[y];
            if(z>0){
                if(x>y)in[x]+=z,out[y]+=z,f[x]+=z;
                else out[x]+=z,in[y]+=z,f[x]+=z;
            }
            else{
                z=-z;
                if(x>y)in[y]+=z,out[x]+=z,f[x]-=z;
                else out[y]+=z,in[x]+=z,f[x]-=z;
            }
        }
    }
    fo(i,1,n){
        j=min(in[i],out[i]),in[i]-=j,out[i]-=j;
        while(in[i])in[i]--,c[++c[0]]=i;
        while(out[i])out[i]--,b[++b[0]]=i;
    }
    printf("%d\n",b[0]);
    fo(i,1,b[0])printf("%d %d\n",b[i],c[i]);
}
版权声明:本文为doyouseeman原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/doyouseeman/article/details/77439924

智能推荐

SpringBoot 使用freemarker 处理文档,找不到文件位置(报错:basePackagePath=““ /* relatively to resourceLoaderClass pkg)

在Spring Boot中加载word的文档的时候,加载ftl文档的位置应该是从 target目录下面去加载的(不太确定),不是像大多数情况这样根据类的路径去加载。SpringBoot加载的位置应该是从 “resources”文件下面开始,如果放到“resources”的根目录下面需要加一道“/”斜线。 类似于: config...

剑指offer 合并两个排序的链表

题目 链接:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/ 思路 我想的是,与合并两个有序数组一样的思维,新建一个链表,然后判断谁的值大,进而在新的链表上面进行插入。 看书思路 合并链表是一个递归问题:合并一个节点后可以转化为一个子问题。终止条件是其中一个链表为空 代码 链表反转也可以用递归解决...

Java编程思想 第三章:操作符

Java中的操作符和c/c++中的操作符基本一致,因为我之前学习过C语言和C++,所以本章的内容大部分都已熟知,下面只做简单的介绍。 Java操作符及优先级 Java中的操作符包括算术操作符,关系操作符,逻辑操作符,位运算符、自操作运算符、移位运算符、赋值运算符和其他运算符。 算术操作符:包括加减乘除和取余(%),优先级乘除取余高于加减,都是双元运算符,其中加法(+)可以用来连接两个字符串,比如:...

JetBrains 系列开发工具,如何配置 `SCSS` `File Watcher` ,相关输出配置参数详解:webStorm phpStorm IDEA

JetBrains 系列开发工具,如何配置 SCSS File Watcher ,相关输出配置参数详解:webStorm phpStorm IDEA 前言 你目前已经了解了如何使用 SCSS 进行开发,了解了该文章的内容:『 SCSS 日常用法 』 在 JetBrains 系列开发工具中通过 FileWatcher 进行编译的 SCSS 文件都是通过 sass 这个程序进行的。『 如何添加 Fil...

C语言小函数—二进制与十六进制

测试如下 “` int main() { long int num = 15; } “`...

猜你喜欢

仿微博或微信的文章多图显示(自定义MultiImageView)

按照一般的规矩,先上张图来供大伙看看 如果大致是大伙们需要实现的功能,不烦一观 自定义MultiImageView 工具类 具体使用 app.gradle中添加依赖 implementation 'com.github.bumptech.glide:glide:4.8.0' AndroidManifest.xml中配置联网权限 <uses-permission android:name=&q...

经典进程同步和互斥问题

经典进程同步与互斥问题 前言 一、生产者-消费者问题 1.问题描述 2.问题分析 3.代码 二、读者-写者问题 1.问题描述&&分析 2.代码 三、哲学家进餐问题 1.问题描述&&分析 2.代码 四、理发师问题 1.问题描述&&分析 2.代码 前言 在多道程序设计环境中,进程同步是一个非常重要的问题,下面讨论几个经典的进程同步问题。 一、生产者-消费...

java设计模式——ThreadLocal线程单例

1、定义一个ThreadLocal线程单例,代码如下: 2、定义一个多线程类,代码如下: 3、定义一个测试类,代码如下: 4、输出结果,如下图:...

【tensorflow】线性模型实战

线性模型:y = 1.477 * x + 0.089   1. 采样数据 采样噪声eps在均值0,方差0.01的高斯分布中,而后在均匀分布U(0,1)中,区间[-10,10]进行n=100次随机采样:   2. 计算误差 循环计算每个点的预测值与真是值之间差的平方并累加,从而获得训练集上的均芳误差损失值。   3. 计算梯度   4. 梯度更新 对权重w和偏...

常见损失函数和评价指标总结(附公式&代码)

网上看到一篇很实用的帖子关于常见损失函数和评价指标,收藏下来 本文转载于https://zhuanlan.zhihu.com/p/91511706 ------------------------------------------------------------------------------------------------------------------------------...