POI2014 FAR-FarmCraft 树形DP+贪心

anyixing-fly 2020-04-06 原文

题目链接 https://www.luogu.org/problem/P3574

题意

翻译其实已经很明确了

分析

这题一眼就是贪心啊，但贪心的方法要思索一下，首先是考虑先走时间多的子树，但不太现实，因为时间跟点的个数也有关系，而且很有可能另外一棵子树不去走会闲置很长时间，就是这棵子树本来可以走一遍然后在子树装软件的时候去走别的树，所以不能这么贪心。那，要怎么办呢？
对于一棵子树，我们必须要走的是跑路时间，而安装可以在去别的子树走的时候干，所以我们肯定要先弄安装时间-跑路时间最大的子树，因为这样的话，我们就可以在它安装的时候去弄别的子树，证明用反证法，先弄别的子树最后时长一定大于先弄它，所以跑完每一个子树后，把它的安装时间和跑路时间扔到堆里，最后把堆取完，就完了，状态转移方程\(DP[u]=max(DP[son]+g[u]+1)\)，g数组记录的跑路时间。

细节问题

首先呢，longlong不需要，爆不掉。
然后是加边，加单向边会出问题，加完图可能不连通，所以只能加双向边，加双向边数组要开2倍啊啊啊啊啊，本蒟蒻忘开然后RE了，接着我把5e5改成了6e5，还RE，然后我以为递归炸了，调了半天，我是不是傻。。。。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=6e5+10;
struct Edge{
    int nxt,to;
}e[N<<1];
int Head[N],len;
void Ins(int a,int b){
    e[++len].to=b;e[len].nxt=Head[a];Head[a]=len;
}
struct Node{
    int f,siz;
    Node(){}
    Node(int a,int b){f=a,siz=b;}     
    bool operator < (const Node&A)const{
        return f-siz<A.f-A.siz;
    }
};
int dp[N],g[N],val[N],que[N];
void dfs(int u,int fa){
    priority_queue<Node> q;
    if(u-1)dp[u]=val[u];
    for(int i=Head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);q.push(Node(dp[v],g[v]));
    }
    while(!q.empty()){
        Node now=q.top();q.pop();
        dp[u]=max(dp[u],now.f+g[u]+1);
        g[u]+=now.siz+2;
    }
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>val[i];
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        Ins(a,b);Ins(b,a);
    }
    dfs(1,0);
    cout<<max(dp[1],val[1]+g[1]);
    return 0;
}