【AtCoder Grand Contest 007 E】Shik and Travel
二分答案，双指针。
题目大意：
给定一棵带权有根二叉树，$1$ 为根结点。每个非叶子结点有两个儿子。
现在你要从 $1$ 出发，走到一个叶结点。然后每次从一个叶结点走到另一个叶结点。最后从叶结点返回 $1$。要求每条边恰好经过 $2$ 次，每个点都经过。
定义一种遍历方案的代价为，除了 $1$ 出发和 $1$ 停止的路径，其他的叶结点到叶结点的路径中，路径长度最长的那一条的长度。
求这个长度的最小值。
题解：
最小化最大值，考虑二分答案。
对于一个非叶子结点，由于它有且仅有两个儿子，所以它一定是选择一个儿子向下走，然后从另一个儿子走上来。
我们令三元组 $(x,l,r)$ 表示当前结点为 $x$，有一种方案，其从一个儿子走到底部的链的长度为 $l$，从另一个儿子的子树底部走上来的链的长度为 $r$，并且其中间的路径的长度都不超过当前二分的答案 $ans$。
对于两个三元组 $(x,l_1,r_1)$ 和 $(x,l_2,r_2)$，若 $l_1\leq l_2,r_1\leq r_2$，则显然保留第一个三元组就可以了。
考虑合并结点 $x$ 的两个结点的儿子的三元组，以获得当前结点的三元组。
由于 $l$ 单调递增，$r$ 单调递减，所以我们可以用双指针合并两个三元组。
两个三元组 $(son_1,l_1,r_1)$ 和 $(son_2,l_2,r_2)$ 若满足 $r_1+l_2\leq ans$（即从左边上来从右边下去形成完整的路径不超过答案），则可以合并为 $(x,l_1,r_2)$。
每层的合并复杂度为 $O(n)$。
通过启发式合并的分析方式可得，每次的复杂度为 $O(n\log n)$。
外面有二分答案，所以总时间复杂度 $O(n\log^2 n)$。
Code：
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int N=131072;
int ch[N][2],t0t[N],fa[N],n,V[N];
typedef vector<pair<LL,LL> >VPII;
void merge(VPII&L,VPII&R,VPII&vec,const LL&lim){
for(int i=0,it=0;i<L.size();++i){
while(it+1<R.size()&&L[i].second+R[it+1].first<=lim)++it;
if(it==R.size())break;
if(L[i].second+R[it].first<=lim)vec.push_back(make_pair(L[i].first,R[it++].second));
}
}
void dfs(int now,LL lim,VPII&vec){
if(t0t[now]==0){
if(V[now]<=lim)vec.push_back(make_pair(V[now],V[now]));
return;
}
VPII L,R,Lv,Rv;
dfs(ch[now][0],lim,L),dfs(ch[now][1],lim,R);
merge(L,R,Lv,lim),merge(R,L,Rv,lim);
int it1=0,it2=0;
while(it1<Lv.size()&&it2<Rv.size())
if(Lv[it1].first<Rv[it2].first){
vec.push_back(Lv[it1]);
++it1;
}else
if(Lv[it1].first>Rv[it2].first){
vec.push_back(Rv[it2]);
++it2;
}else{
Lv[it1].second=min(Lv[it1].second,Rv[it2].second);
vec.push_back(Lv[it1]);
++it1,++it2;
}
while(it1<Lv.size()){
vec.push_back(Lv[it1]);
++it1;
}
while(it2<Rv.size()){
vec.push_back(Rv[it2]);
++it2;
}
for(auto&i:vec)i.first+=V[now],i.second+=V[now];
}
bool check(LL x){
VPII vp;
dfs(1,x,vp);
return!vp.empty();
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=2;i<=n;++i){
cin>>fa[i];
cin>>V[i];
ch[fa[i]][t0t[fa[i]]++]=i;
}
LL l=0,r=1145141919810,ans=r;
while(l<=r){
const LL mid=l+r>>1;
if(check(mid))r=(ans=mid)-1;else l=mid+1;
}
cout<<ans<<'\n';
return 0;
}