[POI 21 Stage 3] FarmCraft

作法：

以下記每個點安裝的時間為 t[ i ]。記 dp[ u ]代表目前在 u ，並且要讓 u 的所有子節點都安裝完成的最少時間。那麼第一個要考慮的就是 u 花的時間，如果 u 不是 1 ，那麼就是 t[ u ] ，否則就是 2 * ( n - 1 ) + t[ u ] 。再來則是要依序完成 u 的子樹們，對於每個子樹，我們需要的資訊有「從 u 走進去走完一圈再出來的時間」和「子樹完成安裝的時間」，後者顯然就是子樹的 dp 值，而前者則不難證明就是子樹的大小 * 2 。所以這個問題就等價於：現在有 m 個工作，每個工作有交代時間 ( 子樹的大小 * 2 ) 和執行時間 ( 子樹的 dp 值 )，必須交代完一個工作才能交代下一個工作，並且從交代的那一刻開始執行，求所有工作執行結束的最少時間。而這就是經典的 greedy ，因為可以把「從交代的那一刻開始執行」改成「從交代完再開始執行，執行 (子樹 dp 值 - 子樹大小 * 2 ) 的時間」，所以只要按照轉換後的執行時間由大到小排序，依序完成每個子樹就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10 ;
 
struct P
{
     int id,val ;
     bool operator < (const P &rhs) const
     {
          return val>rhs.val ;
     }
} tmp[maxn] ;
 
vector<int> v[maxn] ;
int t[maxn],sz[maxn],dp[maxn] ;
 
void dfs(int x,int f)
{
     sz[x]=1 ;
     if(v[x].size()==1 && x!=1) { dp[x]=t[x] ; return ; }
     for(int i=0;i<v[x].size();i++) if(v[x][i]!=f)
          dfs(v[x][i],x) , sz[x]+=sz[v[x][i]] ;
     int cnt=0 ;
     for(int i=0;i<v[x].size();i++) if(v[x][i]!=f)
          tmp[cnt++]=(P){v[x][i],dp[v[x][i]]-2*sz[v[x][i]]} ;
     sort(tmp,tmp+cnt) ;
 
     int ret= (x==1 ? 2*(sz[x]-1)+t[x] : t[x]) ;
     for(int i=0 , sum=0;i<cnt;i++)
     {
          ret=max(ret,sum+1+dp[tmp[i].id]) ;
          sum+=2*sz[tmp[i].id] ;
     }
     dp[x]=ret ;
}
 
main()
{
     int n ; scanf("%d",&n) ;
     for(int i=1;i<=n;i++) scanf("%d",&t[i]) ;
     for(int i=1;i<n;i++)
     {
          int x,y ; scanf("%d%d",&x,&y) ;
          v[x].push_back(y) ;
          v[y].push_back(x) ;
     }
     dfs(1,1) ;
     printf("%d\n",dp[1]) ;
}