2020.2.3

动态规划（一）树上DP

P3574 农场物语

题目描述

在一个叫做比特村的小村庄中，有n-1条路连接着这个村庄中的全部n个房子。

每两个房子之间都有一条唯一的通路。这些房子的编号为1至n。

1号房子属于村庄的管理员比特安萨尔。

为了提升村庄的科技使用水平，n台电脑被快递到了比特安萨尔的房子。每个房子都应该有一台电脑，且分发电脑的任务就落在了比特安萨尔的肩上。

比特村的居民一致同意去玩农场物语这个游戏的最新快照版，而且好消息是他们很快就要得到他们最新的高配置电脑了。他的汽油恰好够走每条路两遍。

在每个房子边，比特安萨尔把电脑贴心的配送给居民，且立即前往下一个房子。（配送过程不花费任何时间）

只要每间房子的居民拿到了他们的新电脑，它们就会立即开始安装农场物语。安装农场物语所用的时间都是已知的。

在比特安萨尔配送完所有电脑后，他会回到他自己的1号房子去安装他自己的农场物语。

用卡车开过每条路的时间恰好是1分钟，请你帮助比特安萨尔算出从开始配送到所有居民都玩上了农场物语的最少时间。

输入格式：

第一行包含一个整数n(2≤n≤500000)，代表比特村中有多少房子。

第二行包含n个整数c₁,c₂,⋯,c_n(1≤c_i≤10⁹)，每个数都被单个空格隔开。c_i是第i号房间中居民安装农场物语所用的时间。

接下来的n-1行代表了每一条路的两个顶点。两个顶点aa和bb满足(1≤a<b≤n)，两个数之间有一个空格。

输出格式：

一行，包含一个整数，代表题目中所说的最小时间。

输入样例

6
1 8 9 6 3 2
1 3
2 3
3 4
4 5
4 6

输出样例

题解

树上DP：围绕子树设计状态，用子树状态转移到当前状态

分析得：每条路走两遍也就是DFS一遍，所以不用记录每条路走的次数

在dfs的同时处理h数组，存储对应子树遍历一次的路程，h的边界就是叶子节点的路程为0（叶子节点的子树没有边），父亲的路程是所有儿子子树路程+1的总和（加的1就是每个儿子到父亲的边）注：这里的h存的是单程

策略：按照子树在管理员离开后需要的时间降序排列，这样就能保证越靠后遍历的子树，管理员离开后所需时间越短，保证了最终答案最小。

在这个顺序基础上，使管理员这样运行，最后该子树答案就是最后一个完成安装的儿子的子树的完成时间或当前节点完成时间。

递归边界：叶子：f[i]=c[i]（不需要路程，安装是唯一任务）

老师的标程+批注+魔改

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define mset(a,b) memset(a,b,sizeof a)
#define lb(x) ((x)&(-(x)))
#define inf 0x3f3f3f3f
#define N 500010
using namespace std;
typedef long long ll;
int n,now,ret;
long long c[N]/*单点完成时间*/,f[N]/*路程+安装最后完成时间*/,h[N]/*路程时间*/;
vector<int> g[N];/*树*/
char buf[15000010];//读入需要
inline int get(){//在buf里快读，不用多做解释
    ret=0;
    while(buf[now]<'0'||buf[now]>'9')now++;
    while(buf[now]>='0'&&buf[now]<='9')ret=ret*10+buf[now]-'0',now++;
    return ret;
}
inline bool cmp(const int a,const int b) {
	return (f[a]-(2*h[a]+2/*加的2是从当前节点的父亲往返当前节点的那一条边的两次路过*/)>f[b]-(2*h[b]+2));//比较全部安装时间减去路程时间的长短（管理员离开后安装需要的时间），a大就返回true，b大返回false
}
inline void dfs(int x,int p) {//x是当前节点，p是父亲
    int t[g[x].size()+1],cnt=0;//t是，cnt记录
    for(int i=0;i<g[x].size();i++) {//枚举每一个相邻节点
        int th=g[x][i];//处理当前相邻节点
        if(th!=p) {//不是父亲
            dfs(th,x);//搜儿子
            h[x]+=h[th]+1;//当前x子树所用时间就是每一个th子树时间加一的累加
            t[++cnt]=th;//记录儿子们
        }
    }
    if(!cnt){//（dfs没搜到）是叶子
        f[x]=c[x];
        return;//子树安装时间就是自己安装时间
    }
    sort(t+1,t+1+cnt,cmp);//按照定义的cmp规则排序
    long long now=0,tmp=0;//两个数分别是当前时间和比较过程中的暂存时间
    for(int i=1;i<=cnt;i++) {//按照排好序的顺序发放
        tmp=max(tmp,now+1+f[t[i]]);//记录目前最后的人安装完成的时刻(决定从now开始遍历i子树并返回)
        now+=2*h[t[i]]+2;//时间推移
        tmp=max(tmp,now);//记录最后时刻
    }
    f[x]=tmp;//这个最后时刻就是x子树总用时
    if(x^1)
        f[x]=max(f[x],c[x]);//如果x本身最后安装完，那就x子树的最后安装完成时间就是x完成时间
}
int main(){
    fread(buf,1,15000000,stdin);//读入函数，将stdin流的数据读到buf(读入需要的字符数组)里面，一次1Byte，读1.5E+7次(只要读完stdin，没到1.5E+7也会停)(在cstdio库里)
    n=get();//get()(快读)函数读入一个数
    for(int i=1;i<=n;i++) {//读入安装时间
        c[i]=get();//继续在buf里读
    }
    for(int i=1;i<n;i++) {
        int a=get(),b=get();//连接成树
        g[a].push_back(b);
        g[b].push_back(a);//用vector存储边
    }
    dfs(1,0);//从管理员家开始DFS
    printf("%lld",max(n*2-2+c[1],f[1]));//最后输出答案
    return 0;
}

洛谷网校：动态规划（一）树上DP p3574