[POI2014][樹形DP]FarmCraft
- 2020 年 4 月 6 日
- 筆記
題目
In a village called Byteville, there are houses connected with N-1 roads. For each pair of houses, there is a unique way to get from one to another. The houses are numbered from 1 to . The house no. 1 belongs to the village administrator Byteasar. As part of enabling modern technologies for rural areas framework, computers have been delivered to Byteasar’s house. Every house is to be supplied with a computer, and it is Byteasar’s task to distribute them. The citizens of Byteville have already agreed to play the most recent version of FarmCraft (the game) as soon as they have their computers. Byteasar has loaded all the computers on his pickup truck and is about to set out to deliver the goods. He has just the right amount of gasoline to drive each road twice. In each house, Byteasar leaves one computer, and immediately continues on his route. In each house, as soon as house dwellers get their computer, they turn it on and install FarmCraft. The time it takes to install and set up the game very much depends on one’s tech savviness, which is fortunately known for each household. After he delivers all the computers, Byteasar will come back to his house and install the game on his computer. The travel time along each road linking two houses is exactly 1 minute, and (due to citizens’ eagerness to play) the time to unload a computer is negligible. Help Byteasar in determining a delivery order that allows all Byteville’s citizens (including Byteasar) to start playing together as soon as possible. In other words, find an order that minimizes the time when everyone has FarmCraft installed.
mhy住在一棵有n個點的樹的1號結點上，每個結點上都有一個妹子。
mhy從自己家出發，去給每一個妹子都送一台電腦，每個妹子拿到電腦後就會開始安裝zhx牌殺毒軟體，第i個妹子安裝時間為。
樹上的每條邊mhy能且僅能走兩次，每次耗費1單位時間。mhy送完所有電腦後會回自己家裡然後開始裝zhx牌殺毒軟體。
卸貨和裝電腦是不需要時間的。
求所有妹子和mhy都裝好zhx牌殺毒軟體的最短時間。
輸入格式
The first line of the standard input contains a single integer N(2<=N<=5 00 000) that gives the number of houses in Byteville.
The second line contains N integers C1,C2……Cn(1<= C<=109), separated by single spaces; Ci is the installation time (in minutes) for the dwellers of house no. i.
The next N-1 lines specify the roads linking the houses. Each such line contains two positive integers a and b(1<=a<b<=N) , separated by a single space. These indicate that there is a direct road between the houses no. a and b.
輸出格式
The first and only line of the standard output should contain a single integer: the (minimum) number of minutes after which all citizens will be able to play FarmCraft together.
樣例輸入
6 1 8 9 6 3 2 1 3 2 3 3 4 4 5 4 6 樣例輸出
11 數據範圍與提示
Explanation: Byteasar should deliver the computers to the houses in the following order: 3, 2, 4, 5, 6, and 1. The game will be installed after 11, 10, 10, 10, 8, and 9 minutes respectively, in the house number order. Thus everyone can play after 11 minutes.
If Byteasar delivered the game in the following order: 3, 4, 5, 6, 2, and 1, then the game would be installed after: 11, 16, 10, 8, 6, and 7 minutes respectively. Hence, everyone could play only after 16 minutes,
解說
首先可以明確一個點的安裝時間等於走到這個點的時間+安裝時間，最後總時間就是所有點的時間中最長的。
剛開始做這道題時深受昨天的Salesman影響，覺得還是需要貪心思想（雖然確實是用貪心，但最開始走偏了……），結合樣例一想，突發奇想覺得時間長的肯定是需要先走，那麼我就把所有兒子的時間排個序，先走時間長的，再走時間短的，走下一個的時間中再加上之前走兄弟的子樹的時間即可。
然後呢？喜提38分。
再仔細想想這個貪心確實不對啊。萬一有一個時間很短的兒子，但是這個兒子下面卻還有時間很長的後代，那麼它還是應該先選的。
這不就尷尬了嗎……（萬惡的樣例）
那麼既然這樣，我們就不能先給兒子排序再遍歷，而是應該先遍歷每個兒子再根據遍歷結果排序。
（下文中f[i]代表 i 節點所有子樹中最長的時間，a[i]代表 i 節點的時間，size[i]代表 i 子樹的規模）
假設 u 節點有兒子 x 和 y ，則如果先走 x 的話 u 的時間就為max(f[x]+1,f[y]+2*size[x]+1)；同理，先走 y 的話 u 的時間就為max(f[y]+1,f[x]+2*size[y]+1)，若先安裝x合適，則必有2*size[x]+f[y]+1>2*size[y]+f[x]+1，即f[x]-2*size[y]<f[y]-2*size[x]，既然這樣，我們就按照f[]-size[]排序即可。
（下面的程式碼里還有部分解說）
程式碼
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=500000+5; 4 int t,a[maxn],head[maxn],n,tot,f[maxn],size[maxn],q[maxn]; 5 struct node{ 6 int to,next; 7 }e[2*maxn]; 8 inline int read(){ 9 int s=0,w=1; 10 char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); 13 return s*w; 14 } 15 bool cmp(int x,int y){//比較函數 16 return f[x]-2*size[x]>f[y]-2*size[y]; 17 } 18 void Add(int from,int to){ 19 e[tot].to=to; 20 e[tot].next=head[from]; 21 head[from]=tot; 22 tot++; 23 } 24 void dfs(int u,int fa){ 25 int cnt=0,sum=1;//sum為走u子樹目前的總時間 26 //cnt為兒子的數量 27 if(u==1) f[u]=0; 28 else f[u]=a[u]; 29 size[u]=1;//葉子節點沒有子樹size就會存為1 30 for(int i=head[u];i;i=e[i].next){ 31 int v=e[i].to; 32 if(v!=fa){ 33 dfs(v,u); 34 size[u]+=size[v];//統計規模 35 } 36 } 37 for(int i=head[u];i;i=e[i].next) if(e[i].to!=fa) q[++cnt]=e[i].to; 38 //q數組一定要用一個，不要一個dfs開一個，會直接爆掉（親身經歷） 39 sort(q+1,q+1+cnt,cmp);//貪心排序 40 for(int i=1;i<=cnt;i++){ 41 f[u]=max(f[u],f[q[i]]+sum); 42 sum+=2*size[q[i]]; 43 } 44 } 45 int main(){ 46 tot=1; 47 n=read(); 48 for(int i=1;i<=n;i++) a[i]=read(); 49 for(int i=1;i<=n-1;i++){ 50 int x=read(),y=read(); 51 Add(x,y); 52 Add(y,x); 53 } 54 dfs(1,0); 55 printf("%d",max(f[1],a[1]+2*(n-1))); 56 return 0; 57 }
View Code
幸甚至哉，歌以詠志。
