【AtCoder Grand Contest 007 E】Shik and Travel | Mrsrz's blog

二分答案，双指针。

题目大意：

给定一棵带权有根二叉树，$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;
}