[ZeroJudge] e201: 期末打掃

題目連結:https://zerojudge.tw/ShowProblem?problemid=e201

---

稀有的過來寫個解。大學生活好累，每天都在被作業QAQ
一開始看錯題目了，不過因為沒看錯太多所以改個幾行就過了XD
看到這題我的第一個想法是樹DP，所以想說先想想看有沒有甚麼有用的性質。感受了一下發現我可以定義$f_u(x)$代表在$x$時間點進入$u$後再出來的時間點，那可以發現$f_u(x)=\max(a_{u0},x+d_u)$，其中$d_u$代表可以不用等待就都檢查完$u$的子樹的時間，$a_{u0}$代表如果是第0個時間點就從$u$出發那要多久後才能回到$u$並把所有教室都檢查完的時間。證明這部分成立的方法也很簡單(不過我很笨想了很久QAQ)，假設在時間點$t\geq 0$，存在一種走法最佳，那我們可以知道他的時間一定$\geq t+d_u$，因為不管怎樣我們至少一定要把底下整棵子樹都走過一遍才能回來，另外我們也知道那個最佳走法的時間也$\geq a_{u0}$，因為如果他更小的話，我們在時間點$0$的時候就可以故意等到時間點$t$在走，這樣可以走出更加的解，與假設不合，這樣我們就證明了在任意時間點$t$的任意解$g$都有$g \geq f_u(t)$，而且明顯$f_u(t)$是可以達到的，因為我們可以照著$t=0$的路徑走，那如果中間很順利不用逗留的話就達到了$f_u(x)=x+d_u$，而若是要逗留的話，那在逗留的當下我們接著的時間就會跟$t=0$的時候同步了，所以這時$f_u(x)=a_{u0}$。
講了這麼多我們現在終於知道一個人在時間點$x$進入$u$後出來的時間，那接下來就是要決定當我們在$u$的時候該以怎樣的順序走訪他的子樹們$v$了，而這時我盯著$f_u(x)=\max(a_{u0},x+d_u)$的圖(一堆平移過後的ReLU函數w)一段時間後猜想順序就是按著$f_u$的轉折點的$x$座標由小到大拜訪就會是好的，也就是按照$a_{u0}-d_u$由小到大走訪就會是最佳的，不過這部分我證不太出來，所以後來就依靠Z3證明了對於任意$s,t,x_0\geq 0$都有$a_{s0} - d_s \leq a_{t0} - d_t \Rightarrow f_t(f_s(x_0)) \leq f_s(f_t(x_0))$，那我們就可以接著證如果存在一組最佳解，那我們交換他相鄰逆序的部分也不會比較差，所以透過照著$a_{u0}-d_u$排序的解一定只會跟最佳解一樣好。
以上，再稍微處理一下從子樹上來的時候的函數值，我們就可以開心$O(TN\log{N})$的做完這題了XD
p.s 話說有沒有人要教我證我用Z3證的那個式子QAQ

#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;
const int N = 50000 + 5;

lld d[ N ];
vector< pair< int, lld > > G[ N ];

pair< lld, lld > dfs( int, int );

int main() {
 ios_base::sync_with_stdio( false );
 cin.tie( nullptr );
 int t; cin >> t;
 while ( t -- ) {
  int n; cin >> n;
  for ( int i = 2 ; i <= n ; ++ i )
   cin >> d[ i ];
  for ( int i = 2 ; i <= n ; ++ i ) {
   int u, v, w; cin >> u >> v >> w;
   G[ u ].emplace_back( v, w );
   G[ v ].emplace_back( u, w );
  }
  lld a, w; tie( a, w ) = dfs( 1, 1 );
  cout << max( a, w ) << '\n';
  for ( int i = 1 ; i <= n ; ++ i )
   G[ i ].clear();
 }
 return 0;
}

pair< lld, lld > dfs( int u, int f ) {
 vector< pair< lld, lld > > sub;
 lld y = 0, w = 0;
 for ( auto e : G[ u ] ) {
  if ( e.first == f ) continue;
  sub.push_back( dfs( e.first, u ) );
  sub.back().first += e.second;
  sub.back().second += e.second * 2;
  w += sub.back().second;
 }
 sort( sub.begin(), sub.end(), []( const pair< lld, lld >& a, const pair< lld, lld >& b ) {
  return a.first - a.second < b.first - b.second;
 } );
 for ( auto s : sub ) y = max( s.first, s.second + y );
 return { max( y, d[ u ] ), w };
}