POI2014 FarmCraft

FarmCraft

POI2014

题意

1.有一棵n个节点的树

2.有个人在1号节点上

3.每个节点有一台电脑，安装软件需要C[i]的时间

4.现在树上的每条边只能被走两次，每次耗时1分钟

5.当这个人第一次走到节点x时，他会自动开始安装软件

6.这个人必须让所有电脑开始安装后，回到自己的家里亲自安装自己的电脑

7.问所有电脑都安装完毕的最短时间是多少

解

1.由“树上的每条边仅能走两次”得，每棵子树只能遍历一次，必须一次性遍历完

2.树形dp dp[x]:处理完x的子树，回到x点最少要等多少分钟

3.先存下所有子树的(dp[y],sz[y]*2)

4.子树的合并
贪心的合并，使决策最优
对于两个子树a,b
如果先a在b 总时间为：dp[a],sz[a]*2+dp[b]
如果先b在a 总时间为：dp[b],sz[b]*2+dp[a]

因此先存下所有子树的(dp[y],sz[y]*2)
按dp+tmp.sz<tmp.dp+sz排序，从小到大

5.dp[x]=max(C[x],dp[y]+sum(sz))

具体代码

#include<bits/stdc++.h>
using namespace std;
const int M=500005;
struct node{
    int ti,sz;
    bool operator <(const node&tmp)const{
        return sz+tmp.ti<tmp.sz+ti;
    }
}A[M];
int n,C[M];
int head[M],asdf;
struct edge {
    int to,nxt;
} G[M*2];
void add_edge(int a,int b) {
    G[++asdf].to=b;
    G[asdf].nxt=head[a];
    head[a]=asdf;
}
int dp[M],sz[M],len;
void dfs(int x,int f) {
    sz[x]=1;
    for(int i=head[x]; i; i=G[i].nxt) {
        int y=G[i].to;
        if(y==f)continue;
        dfs(y,x);
        sz[x]+=sz[y];
    }
    len=0;
    for(int i=head[x];i;i=G[i].nxt){
        int y=G[i].to;
        if(y==f)continue;
        A[++len]=(node){dp[y]+1,sz[y]*2};
    }
    sort(A+1,A+1+len);
    int sum=0,mx=(sz[x]-1)*2;
    for(int i=1;i<=len;i++){
        mx=max(mx,A[i].ti+sum);
        sum+=A[i].sz;
    }
    dp[x]=max(C[x],mx);
}
int main() {
    int a,b;
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d",&C[i]);
    }
    for(int i=1; i<n; i++) {
        scanf("%d %d",&a,&b);
        add_edge(a,b);
        add_edge(b,a);
    }
    dfs(1,0);
    dp[1]=max(dp[1],C[1]+(n-1)*2);
    printf("%d\n",dp[1]);
    return 0;
}