【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

智能推荐

phpstudy的mysql版本升级至5.7

phpstudy安装的mysql版本一般都是5.5或5.4的,但是有时候做项目又必须用到mysql5.7版本,所以我们现在来看一下如何在phpstudy的环境下将mysql版本升级至5.7   温馨提醒: 先删掉所有环境变量,如果是之前有的话,不然怎么安装cmd上指向的还是原来的版本。安装完再设新的环境变量。 并且卸载掉mysqld服务mysqld remove。如果不先删除的话,可能会...

RIP/DHCP/ACL综合实验

组播: 加入组的组成员才会接受到消息,只需要将流量发送一次到组播地址 减少控制面流量,减少头部复制, RIP1  广播   有类  不支持认证 RIP2  组播   无类  (支持VLAN)、支持认证 所有距离矢量路由协议:具有距离矢量特征的协议,都会在边界自动汇总 控制平面  路由的产生是控制平面的流量 数据平面  ...

【Sublime】使用 Sublime 工具时运行python文件

使用 Sublime 工具时报Decode error - output not utf-8解决办法   在菜单中tools中第四项编译系统 内最后一项增添新的编译系统 自动新建 Python.sublime-build文件,并添加"encoding":"cp936"这一行,保存即可 使用python2 则注释encoding改为utf-8 ctr...

java乐观锁和悲观锁最底层的实现

1. CAS实现的乐观锁 CAS(Compare And Swap 比较并且替换)是乐观锁的一种实现方式,是一种轻量级锁,JUC 中很多工具类的实现就是基于 CAS 的,也可以理解为自旋锁 JUC是指import java.util.concurrent下面的包, 比如:import java.util.concurrent.atomic.AtomicInteger; 最终实现是汇编指令:lock...

Python 中各种imread函数的区别与联系

  原博客:https://blog.csdn.net/renelian1572/article/details/78761278 最近一直在用python做图像处理相关的东西,被各种imread函数搞得很头疼,因此今天决定将这些imread总结一下,以免以后因此犯些愚蠢的错误。如果你正好也对此感到困惑可以看下这篇总结。当然,要了解具体的细节,还是应该 read the fuc...

猜你喜欢

用栈判断一个字符串是否平衡

注: (1)本文定义:左符号:‘(’、‘[’、‘{’…… 右符号:‘)’、‘]’、‘}’……. (2)所谓的字符串的符号平衡,是指字符串中的左符号与右符号对应且相等,如字符串中的如‘(&r...

JAVA环境变量配置

位置 计算机->属性->高级系统设置->环境变量 方式一 用户变量新建path 系统变量新建classpath 方式二 系统变量 新建JAVA_HOME,值为JDK路径 编辑path,前加 方式三 用户变量新建JAVA_HOME 此路径含lib、bin、jre等文件夹。后运行tomcat,eclipse等需此变量,故最好设。 用户变量编辑Path,前加 系统可在任何路径识别jav...

常用的伪类选择器

CSS选择器众多 CSS选择器及权重计算 最常用的莫过于类选择器,其它的相对用的就不会那么多了,当然属性选择器和为类选择器用的也会比较多,这里我们就常用的伪类选择器来讲一讲。 什么是伪类选择器? CSS伪类是用来添加一些选择器的特殊效果。 常用的为类选择器 状态伪类 我们中最常见的为类选择器就是a标签(链接)上的为类选择器。 当我们使用它们的时候,需要遵循一定的顺序问题,否则将可能出现bug 注意...

ButterKnife的使用介绍及原理探究(六)

前面分析了ButterKnife的源码,了解其实现原理,那么就将原理运用于实践吧。 github地址:       点击打开链接 一、自定义注解 这里为了便于理解,只提供BindView注解。 二、添加注解处理器 添加ViewInjectProcessor注解处理器,看代码, 这里分别实现了init、getSupportedAnnotationTypes、g...

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。考试复习题库1|要求:只能使用单字符比较操作。

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。 要求只能使用单字符比较操作。 参考代码: 实验结果截图:...