[DP记录]AT2172 [AGC007E] Shik and Travel

**题意** ： 一颗 $n$ 个节点的二叉树，每个节点要么有两个儿子要么没有儿子。边有边权。 第一天，你从 $1$ 号节点出发，走到一个叶子节点。然后每一天，你可以从当前点走到另一个叶子。 最后一天需要回到 $1$ 号节点。要求到过所有叶子并且每条边经过**恰好**两次。 每天的路费是你走过的路径上的边权和，你的公司会为你报销大部分路费，除了你旅行中所用路费最高的，且行走路线是从叶子到叶子的那一天的路费。 求你自己最少要付多少路费？ $n\leq 2^{17}$ ，时限$\texttt{5s}$。 ------------ 牛逼题。 考虑二分答案，问题变成判定是否存在每一天路费都不超过 $lim$ 的方案。 由于每条边恰好经过两次，每个子树只能进出各一次，必须要走完所有叶子才能离开。 设 $f[u,a,b]$ 为 ： 处理 $u$ 的子树，第一个叶子到根的距离不超过 $a$，最后一个叶子到根的距离不超过 $b$ ，中间的路径都不超过 $lim$ 的方案是否存在。 显然有 $f[u,a,b]=f[u,b,a]$。 记 $l,r$ 分别为 $u$ 的左右儿子， $vl,vr$ 分别为到左右儿子的距离。 转移时有 ： $$f[u,b,a]=f[u,a,b]={\rm AND}_{i,j}f[l,a,i]f[r,j,b]\big[i+j+vl+vr\leq lim\big]$$ 若 $f[1,\_,\_]$ 中存在 $1$ ，那么 朴素实现复杂度交劣，考虑简化状态，优化转移。 若 $f[u,a_1,b_1]=1$ ，那么所有 $f[u,a_2,b_2](a_1\leq a_2,b_1\leq b_2)$ 均为 $1$。 于是只需要记录 $(a_1,b_1)$ 的“下包络线”。 记 $g[u,a]=\min_{f[u,a,b]=1}b$ ，即每个 $a$ 对应的 $b$ 的最小值。 同时，若 $g[u,a-1]=g[u,a]$ 那么 $g[u,a]$ 是不必处理的（即考虑为分段函数）。 转移为 ： $$g[u,a]=\min\bigg(\min_{j\leq lim-vl-vr-g[l,a]}g[r,j],\min_{j\leq lim-vl-vr-g[r,a]}g[l,j]\bigg)$$ 设分段函数 $g[l,\_],g[r,\_]$ 的段数分别为 $s_l,s_r$。 每个 $g[l,a]$ 都只会对应唯一一个 $g[r,j]$ ，故 $s_u=2\min(s_l,s_r)$。 类似启发式合并的复杂度分析，分段函数总段数是 $O(n\log n)$ 的。 考虑如何计算 $\min\limits_{j\leq lim-vl-vr-g[l,a]}g[r,j]$ 对应的分段函数。显然，指针单调扫描即可。 求两个单调函数的 $\min$ 的过程类似于归并。 这样，就能以 $O(n\log n)$ 的复杂度完成判定，总复杂度为 $O(n\log n\log v)$。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #define pb push_back #define ll long long #define MaxN 140000 using namespace std; struct Node{int l,r,lv,rv;}t[MaxN]; struct Data{ll a,b;}; #define Hull vector<Data> void get(Data *st,Hull &C,int n) { for (int i=0;i<n;i++) if(C.empty()||C.back().b>st[i].b)C.pb(st[i]); } Hull p[MaxN]; Data st[MaxN]; void add(const Hull &A,const Hull &B,ll lim,Hull &C) { int p=-1,tn=0; for (int i=0;i<A.size();i++){ while(p+1<B.size()&&A[i].b+B[p+1].a<=lim)p++; if (p>=0)st[tn++]=(Data){A[i].a,B[p].b}; }get(st,C,tn); } bool cmp(const Data &A,const Data &B) {return A.a<B.a;} void min(const Hull &A,const Hull &B,Hull &C) { merge(A.begin(),A.end(),B.begin(),B.end(),st,cmp); get(st,C,A.size()+B.size()); } ll lim; void dfs(int u) { if (!t[u].l){p[u].pb((Data){0,0});return ;} dfs(t[u].l);dfs(t[u].r); Hull s1,s2; add(p[t[u].l],p[t[u].r],lim-t[u].lv-t[u].rv,s1); for (int i=0;i<s1.size();i++) {s1[i].a+=t[u].lv;s1[i].b+=t[u].rv;} add(p[t[u].r],p[t[u].l],lim-t[u].lv-t[u].rv,s2); for (int i=0;i<s2.size();i++) {s2[i].a+=t[u].rv;s2[i].b+=t[u].lv;} min(s1,s2,p[u]); } int n; bool chk() { for (int i=1;i<=n;i++)p[i].clear(); dfs(1); return p[1].size(); } int main() { scanf("%d",&n); for (int i=2,fa,v;i<=n;i++){ scanf("%d%d",&fa,&v); if (t[fa].l){t[fa].r=i;t[fa].rv=v;} else {t[fa].l=i;t[fa].lv=v;} } ll l=0,r=1ll<<35; while(l<r){ lim=(l+r)>>1; if (chk())r=lim; else l=lim+1; }printf("%lld",r); return 0; } ```