像这两种必须走到叶子的路径感觉是必须从INF出发，使得它强制从子树转移过来。否则假如可以在中间节点中断的话，初始值就是0，转移的时候假如子树更不好就不会更新这个0。
与哪个求每个点去往的最远点的标号（同样远的求最小标号）类似。f[u]表示从u节点向下走向子树的最优值，这样必须dfs到叶子然后初始化叶子再返回。
g[u]表示从u节点向上走到父亲p，然后从父亲p绕另一条路（要么是走到祖父，要么是走到兄弟，所以f[p]要记录次优值以及最优值走向哪个儿子）的最优值，dfs的时候初始化根为它本身。这样子定义导致在统计答案的时候要特判。
#includeusing namespace std;typedef long long ll;const int MAXN = 1e5 + 5;ll val[MAXN];vector E[MAXN];int ROOT;void dfs1(int u, int p) { if(E[u].size() == 1) { ROOT = u; return; } for(auto v : E[u]) { if(v == p) continue; dfs1(v, u); if(ROOT != -1) return; }}const ll INF = 1e18 + 1e17;const ll INF2 = 1e16;struct F { ll val; int son;} fm1[MAXN], fm2[MAXN], fM1[MAXN], fM2[MAXN], tmpm, tmpM;inline void InitF(int n) { for(int i = 1; i <= n; ++i) { fm1[i].val = fm2[i].val = INF; fM1[i].val = fM2[i].val = -INF; fm1[i].son = fm2[i].son = fM1[i].son = fM2[i].son = -1; }}void maintainF(int u, int v) { if(tmpM.val < fm2[u].val) { fm2[u] = tmpM; fm2[u].son = v; if(fm2[u].val < fm1[u].val) { swap(fm1[u], fm2[u]); } } if(tmpm.val > fM2[u].val) { fM2[u] = tmpm; fM2[u].son = v; if(fM2[u].val > fM1[u].val) { swap(fM1[u], fM2[u]); } }}void dfsF(int u, int p) { if(E[u].size() == 1 && E[u][0] == p) { fm1[u].val = val[u]; fM1[u].val = val[u]; fm1[u].son = u; fM1[u].son = u; return; } for(auto v : E[u]) { if(v == p) continue; dfsF(v, u); tmpM = fM1[v]; tmpm = fm1[v]; maintainF(u, v); } fm1[u].val += val[u]; fm2[u].val += val[u]; fM1[u].val += val[u]; fM2[u].val += val[u];}struct G { ll val;} gm[MAXN], gM[MAXN];inline void InitG(int n) { for(int i = 1; i <= n; ++i) { gm[i].val = INF; gM[i].val = -INF; }}F getFm(int u, int p) { if(fm1[p].son == u) return fm2[p]; return fm1[p];}F getFM(int u, int p) { if(fM1[p].son == u) return fM2[p]; return fM1[p];}void maintainG(int u, int p) { if(p == -1) { gm[u].val = val[u]; gM[u].val = val[u]; return; } gm[u].val = max(getFM(u, p).val, gM[p].val) + val[u]; gM[u].val = min(getFm(u, p).val, gm[p].val) + val[u];}void dfsG(int u, int p) { maintainG(u, p); for(auto v : E[u]) { if(v == p) continue; dfsG(v, u); }}int main() {#ifdef Yinku freopen("Yinku.in", "r", stdin);#endif // Yinku int T; scanf("%d", &T); while(T--) { int n; scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%lld", &val[i]); for(int i = 1, b; i <= n; ++i) { scanf("%d", &b); val[i] -= b; } for(int i = 1; i <= n; ++i) E[i].clear(); for(int i = 1; i <= n - 1; ++i) { int u, v; scanf("%d%d", &u, &v); E[u].push_back(v); E[v].push_back(u); } ROOT = -1; dfs1(1, -1); //ROOT是其中一个叶子 InitF(n); dfsF(ROOT, -1); InitG(n); dfsG(ROOT, -1); ll ans = -INF; for(int i = 1; i <= n; ++i) { ll tmp = (E[i].size() == 1 && i != ROOT ? INF : fm1[i].val); tmp = min(tmp, (i != ROOT) ? (gm[i].val) : INF); ans = max(ans, tmp); } printf("%lld\n", ans); } return 0;}
假如定义f和g不包含节点本身的话，那是不是不需要特判呢？只能说是判得更恶心了。